Submission #1099121

#TimeUsernameProblemLanguageResultExecution timeMemory
1099121NurislamExamination (JOI19_examination)C++17
0 / 100
125 ms17536 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define ff first #define ss second #define all(x) x.begin(),x.end() #define rall(x) x.rbegin(),x.rend() #define int long long template <class F, class _S> bool chmin(F &u, const _S &v){ bool flag = false; if ( u > v ){ u = v; flag |= true; } return flag; } template <class F, class _S> bool chmax(F &u, const _S &v){ bool flag = false; if ( u < v ){ u = v; flag |= true; } return flag; } const int N = (1<<18) +1, inf = 1e18+200; //int mod = 998244353; //int mod = 1000000007; mt19937 rng(chrono::steady_clock::now().time_since_epoch().count()); #define rnd(l, r) uniform_int_distribution <int> (l, r)(rng) struct segtree{ vector<int> t; segtree(){ t.resize(N*4); }; void upd(int ps, int i = 1, int l = 1, int r = N){ if(l == r){ t[i]++; return; } int m = (l+r)>>1; if(ps <= m)upd(ps, i*2, l, m); else upd(ps, i*2+1, m+1, r); t[i] = t[i*2] + t[i*2+1]; }; int get(int tl, int tr, int i = 1, int l = 1, int r = N){ if(l > tr || r < tl)return 0; if(tl <= l && r <= tr)return t[i]; int m = (l+r)>>1; return get(tl, tr, i*2, l, m)+get(tl, tr, i*2+1, m+1, r); }; }; void solve(){ int n, q; cin >> n >> q; vector<array<int, 2>> v(n); for(auto&[i, j]:v)cin >> i >> j; sort(rall(v)); vector<array<int,3>> que; for(int i = 0; i < q; i++){ int a, b, c; cin >> a >> b >> c; que.pb({a, b, i}); } sort(rall(que)); auto compr = [&]()->void{ vector<int> vv; for(auto [i, j]:v)vv.pb(i),vv.pb(j); for(auto [i, j, k]:que)vv.pb(i), vv.pb(j); sort(all(vv)); vv.erase(unique(all(vv)), vv.end()); for(auto &[i, j]:v){ i = lower_bound(all(vv), i)-vv.begin(); j = lower_bound(all(vv), j)-vv.begin(); } for(auto &[i, j, k]:que){ i = lower_bound(all(vv), i)-vv.begin(); j = lower_bound(all(vv), j)-vv.begin(); } };compr(); //for(auto [i, j]:v)cout << i << ' ' << j << '\n'; //for(auto [i, j, k]:que)cout << i << ' ' << j << ' ' << k << '\n'; vector<int> ans(q); int it = 0; segtree t; for(int i = 0; i < q; i++){ int a = que[i][0], b = que[i][1], id = que[i][2]; while(it < n && v[it][0] >= a){ t.upd(v[it][1]); it++; } ans[id] = t.get(b, N); } for(int i:ans)cout << i << ' '; cout << '\n'; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr); int tt = 1; //cin >> tt; while(tt--){ solve(); } }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...