結果
問題 |
No.3085 Easy Problems
|
ユーザー |
![]() |
提出日時 | 2025-04-04 21:45:23 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 773 ms / 2,000 ms |
コード長 | 13,748 bytes |
コンパイル時間 | 3,894 ms |
コンパイル使用メモリ | 299,620 KB |
実行使用メモリ | 17,520 KB |
最終ジャッジ日時 | 2025-04-04 21:46:06 |
合計ジャッジ時間 | 27,687 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge6 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 31 |
ソースコード
#include <bits/stdc++.h> #include <iostream> #include <vector> #include <string> #include <stack> #include <algorithm> #include <iomanip> #include <chrono> #pragma GCC target ("avx") #pragma GCC optimize("O3") #pragma GCC optimize("unroll-loops") #define rep(i,n) for (ll i = 0;i < (ll)(n);i++) #define Yes cout << "Yes" << "\n"// YESの短縮 #define No cout << "No" << "\n"// NOの短縮 #define rtr0 return(0)//return(0)の短縮 #define gyakugen(x) modpow(x,mod - 2,mod); #define agyakugen(x) modpow(x,amod - 2,amod); using namespace std; //using namespace ranges; using ll = long long;//63bit型整数型 using ld = long double;//doubleよりも長い値を保存できるもの using ull = unsigned long long;//符号がない64bit型整数 ll mod = 998244353; ll amod = 1000000007; ll MINF = -5000000000000000000; ll INF = 5000000000000000000; ll inf = 5000000000; ll minf = -5000000000; ll BAD = -1; vector<ll>tate = {0,-1,0,1};//グリッド上の全探索時の四方向の上下のチェック vector<ll>yoko = {1,0,-1,0};//グリッド上の全探索時の四方向の右左のチェック vector<ll>eightx = {0,-1,-1,-1,0,1,1,1};//グリッド上の全探索時の八方向の上下のチェック vector<ll>eighty = {1,1,0,-1,-1,-1,0,1};//グリッド上の全探索時の八方向の右左のチェック vector<ll>hexsax = {0,1,1,0,-1,-1}; vector<ll>hexsay = {1,1,0,-1,-1,0}; //返り値は素数のリスト。 vector < bool > isprime; vector < ll > Era(int n){//書き方 vector<ll>[] = Era(x); とやるとxまでの素数が出てくる。 isprime.resize(n, true); vector < ll > res; isprime[0] = false; isprime[1] = false; for(ll i = 2; i < n; ++i) isprime[i] = true; for(ll i = 2; i < n; ++i) { if(isprime[i]) { res.push_back(i); for(ll j = i * 2; j < n; j += i) isprime[j] = false; } } return res; } // 素数判定 21~35 long long modpow(long long a, long long n, long long mod) { long long res = 1; while (n > 0) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; } long long npow(long long a, long long n){ long long res = 1; while (n > 0) { if (n & 1) res = res * a; a = a * a; n >>= 1; } return res; } // モッドを使った累乗 template<class T> struct dijkstra{ public: vector<vector<pair<T,T>>>graph; vector<T>ans; priority_queue<pair<T,T>,vector<pair<T,T>>,greater<pair<T,T>>>pq; void do_dijkstra(T start){//頂点xからダイクストラを行う pq.push({0,start}); ans[start] = 0; while(true){ if(pq.empty())break; T cost = pq.top().first; T vertex = pq.top().second; pq.pop(); for(T i = 0;i<graph[vertex].size();i++){ T nextvertex = graph[vertex][i].first; T nextcost = graph[vertex][i].second + cost; if(ans[nextvertex] > nextcost){ ans[nextvertex] = nextcost; pq.push({nextcost,nextvertex}); } } } } void make_indirectedgraph(T u,T v,T cost){//無向辺のグラフ作成 graph[u].push_back({v,cost}); graph[v].push_back({u,cost}); } void make_directedgraph(T u,T v,T cost){//有向辺のグラフ作成 graph[u].push_back({v,cost}); } T output(T end){//答えを出す return ans[end]; } void reset(T N){//リセット graph.clear(); ans.clear(); for(ll i = 0;i<N;i++){ graph.push_back({vector<pair<T,T>>(0)}); ans.push_back(INF); } } }; template<class T> struct unionfind { public: vector<T> parent, rank; void reset(T N) { // 初期化 parent.resize(N); rank.assign(N, 1); // 各集合のサイズを 1 にする for (T i = 0; i < N; i++) parent[i] = i; } T leader(T x) { // 経路圧縮による親の取得 if (parent[x] == x) return x; return parent[x] = leader(parent[x]); // 経路圧縮 } void marge(T x, T y) { // ランクによるマージ T a = leader(x), b = leader(y); if(a!=b){ if (rank[a] < rank[b]) swap(a, b); parent[b] = a; rank[a] += rank[b]; // サイズを更新 } } bool same(T x, T y) { // 同じ集合か判定 return leader(x) == leader(y); } T size(T x) { // 集合のサイズを取得 return rank[leader(x)]; } void check(T N) { // デバッグ用: 親の確認 for (T i = 0; i < N; i++) cout << parent[i] << " "; cout << "\n"; } }; //セグ木 template <class S, S (*op)(S, S), S (*e)()> struct segtree { public: segtree() : segtree(0) {} segtree(int n) : segtree(std::vector<S>(n, e())) {} segtree(const std::vector<S>& v) : _n(int(v.size())){ log = ceil_pow2(_n); size = 1 << log; d = std::vector<S>(2 * size, e()); for (int i = 0; i < _n; i++) d[size + i] = v[i]; for (int i = size - 1; i >= 1; i--) { update(i); } } void set(int p, S x) { assert(0 <= p && p < _n); p += size; d[p] = x; for (int i = 1; i <= log; i++) update(p >> i); } S get(int p) { assert(0 <= p && p < _n); return d[p + size]; } S prod(int l, int r) { assert(0 <= l && l <= r && r <= _n); S sml = e(), smr = e(); l += size; r += size; while (l < r) { if (l & 1) sml = op(sml, d[l++]); if (r & 1) smr = op(d[--r], smr); l >>= 1; r >>= 1; } return op(sml, smr); } S all_prod() { return d[1]; } template <bool (*f)(S)> int max_right(int l) { return max_right(l, [](S x) { return f(x); }); } template <class F> int max_right(int l, F f) { assert(0 <= l && l <= _n); assert(f(e())); if (l == _n) return _n; l += size; S sm = e(); do{ while (l % 2 == 0) l >>= 1; if (!f(op(sm, d[l]))) { while (l < size) { l = (2 * l); if (f(op(sm, d[l]))) { sm = op(sm, d[l]); l++; } } return l - size; } sm = op(sm, d[l]); l++; }while ((l & -l) != l); return _n; } template <bool (*f)(S)> int min_left(int r) { return min_left(r, [](S x) { return f(x); }); } template <class F> int min_left(int r, F f) { assert(0 <= r && r <= _n); assert(f(e())); if (r == 0) return 0; r += size; S sm = e(); do{ r--; while (r > 1 && (r % 2)) r >>= 1; if (!f(op(d[r], sm))) { while (r < size) { r = (2 * r + 1); if (f(op(d[r], sm))) { sm = op(d[r], sm); r--; } } return r + 1 - size; } sm = op(d[r], sm); }while ((r & -r) != r); return 0; } private: int _n, size, log; std::vector<S> d; void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); } int ceil_pow2(int n) { int x = 0; while ((1U << x) < (unsigned int)(n)) x++; return x; } }; //遅延セグ木 template <class S,S (*op)(S, S),S (*e)(),class F,S (*mapping)(F, S),F (*composition)(F, F),F (*id)()> struct lazy_segtree { public: lazy_segtree() : lazy_segtree(0) {} lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {} lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) { log = ceil_pow2(_n); size = 1 << log; d = std::vector<S>(2 * size, e()); lz = std::vector<F>(size, id()); for (int i = 0; i < _n; i++) d[size + i] = v[i]; for (int i = size - 1; i >= 1; i--) { update(i); } } void set(int p, S x) { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); d[p] = x; for (int i = 1; i <= log; i++) update(p >> i); } S get(int p) { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); return d[p]; } S prod(int l, int r) { assert(0 <= l && l <= r && r <= _n); if (l == r) return e(); l += size; r += size; for (int i = log; i >= 1; i--) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push(r >> i); } S sml = e(), smr = e(); while (l < r) { if (l & 1) sml = op(sml, d[l++]); if (r & 1) smr = op(d[--r], smr); l >>= 1; r >>= 1; } return op(sml, smr); } S all_prod() { return d[1]; } void apply(int p, F f) { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); d[p] = mapping(f, d[p]); for (int i = 1; i <= log; i++) update(p >> i); } void apply(int l, int r, F f) { assert(0 <= l && l <= r && r <= _n); if (l == r) return; l += size; r += size; for (int i = log; i >= 1; i--) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push((r - 1) >> i); } { int l2 = l, r2 = r; while (l < r) { if (l & 1) all_apply(l++, f); if (r & 1) all_apply(--r, f); l >>= 1; r >>= 1; } l = l2; r = r2; } for (int i = 1; i <= log; i++) { if (((l >> i) << i) != l) update(l >> i); if (((r >> i) << i) != r) update((r - 1) >> i); } } template <bool (*g)(S)> int max_right(int l) { return max_right(l, [](S x) { return g(x); }); } template <class G> int max_right(int l, G g) { assert(0 <= l && l <= _n); assert(g(e())); if (l == _n) return _n; l += size; for (int i = log; i >= 1; i--) push(l >> i); S sm = e(); do { while (l % 2 == 0) l >>= 1; if (!g(op(sm, d[l]))) { while (l < size) { push(l); l = (2 * l); if (g(op(sm, d[l]))) { sm = op(sm, d[l]); l++; } } return l - size; } sm = op(sm, d[l]); l++; } while ((l & -l) != l); return _n; } template <bool (*g)(S)> int min_left(int r) { return min_left(r, [](S x) { return g(x); }); } template <class G> int min_left(int r, G g) { assert(0 <= r && r <= _n); assert(g(e())); if (r == 0) return 0; r += size; for (int i = log; i >= 1; i--) push((r - 1) >> i); S sm = e(); do { r--; while (r > 1 && (r % 2)) r >>= 1; if (!g(op(d[r], sm))) { while (r < size) { push(r); r = (2 * r + 1); if (g(op(d[r], sm))) { sm = op(d[r], sm); r--; } } return r + 1 - size; } sm = op(d[r], sm); } while ((r & -r) != r); return 0; } private: int _n, size, log; std::vector<S> d; std::vector<F> lz; int ceil_pow2(int n) { int x = 0; while ((1U << x) < (unsigned int)(n)) x++; return x; } void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); } void all_apply(int k, F f) { d[k] = mapping(f, d[k]); if (k < size) lz[k] = composition(f, lz[k]); } void push(int k) { all_apply(2 * k, lz[k]); all_apply(2 * k + 1, lz[k]); lz[k] = id(); } }; //遅延セグ木のベース using lazyS = ll; using lazyF = ll;//型 lazyS e(){ return 0;}//範囲外などを起こしてしまったときの返り値 lazyS op(lazyS a, lazyS b){ return a+b; }//操作したいこと lazyS mapping(lazyF f, lazyS x){ return x+f; }//下まで伝播させたいこと lazyF composition(lazyF f, lazyF g){ return g+f; }//まとめてやった場合おこしたいこと lazyF id(){ return 0; }//遅延セグ木のベース int main(){ //B以上は基本詳細を書いておくと便利 A = ooの値とか 見直す時に便利 // この問題の本質 ll N; cin >> N; unordered_map<ll,vector<ll>>X; vector<pair<ll,ll>>A(N); for(ll i = 0;i<N;i++){ cin >> A[i].first >> A[i].second; } sort(A.begin(),A.end()); vector<ll>B(0); for(ll i = 0;i<N;i++){ B.push_back(A[i].first); X[A[i].second].push_back(A[i].first); } //for(ll i = 1;i<=100000;i++)X[i].push_back(INF); //B.push_back(INF); ll Q; cin >> Q; for(ll i = 0;i<Q;i++){ ll a,b; cin >> a >> b; ll x = upper_bound(B.begin(),B.end(),a)-B.begin(); ll y = upper_bound(X[b].begin(),X[b].end(),a)-X[b].begin(); //cout << X[b].size() << " " << B.size() << "\n"; //cout << y << " " << x << "\n"; cout << x - y << "\n"; } }