Submission #1093533

#TimeUsernameProblemLanguageResultExecution timeMemory
1093533DuckmannnExamination (JOI19_examination)C++17
0 / 100
1272 ms668100 KiB
#include <bits/stdc++.h> #define ll long long #define fr(i, d, c) for(ll i = d; i <= c; i++) #define fl(i, d, c) for(ll i = d; i >= c; i--) const int N = 2e5 + 9; using namespace std; ll n, q, kq[N]; vector<tuple<ll, ll, ll, ll, ll>> qr; vector<ll> nen; struct node { ll nx[2], cnt; }; struct trie { vector<node> t; trie() { t.emplace_back(); } void up(ll x, ll val) { ll cur = 0; for(ll j = 31; j >= 0; j--) { ll y = 0; if(x >> j & 1) y = 1; if(!t[cur].nx[y]) { t[cur].nx[y] = t.size(); t.emplace_back(); } cur = t[cur].nx[y]; t[cur].cnt += val; } } ll get(ll x) { ll cur = 0, ans = 0; for(ll j = 31; j >= 0; j--) { ll y = 0; if(x >> j & 1) y = 1; if(y == 1) { ll z = t[cur].nx[0]; if(z) ans += t[z].cnt; } if(!t[cur].nx[y]) break; cur = t[cur].nx[y]; if(j == 0) ans += t[cur].cnt; } return ans; } } tree[4 * N]; void up(ll pos, ll val, ll num, ll id = 1, ll l = 1, ll r = nen.size()) { if(l == r) { tree[id].up(val, num); } else { ll mid = (l + r) / 2; if(pos <= mid) up(pos, val, num, id * 2, l, mid); else up(pos, val, num, id * 2 + 1, mid + 1, r); tree[id].up(val, num); } } ll get(ll st, ll en, ll f, ll s, ll id = 1, ll l = 1, ll r = nen.size()) { if(st > r || en < l) return 0; if(st <= l && r <= en) return tree[id].get(s) - tree[id].get(f - 1); ll mid = (l + r) / 2; return get(st, en, f, s, id * 2, l, mid) + get(st, en, f, s, id * 2 + 1, mid + 1, r); } int32_t main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cin >> n >> q; fr(i, 1, n) { ll x, y; cin>> x >> y; nen.push_back(y); qr.push_back({x, 1, y, 0, 0}); } fr(i, 1, q) { ll x, y, z; cin>> x >> y >> z; nen.push_back(y); qr.push_back({x, 0, y, z, i}); } sort(nen.begin(), nen.end()); nen.erase(unique(nen.begin(), nen.end()), nen.end()); sort(qr.begin(), qr.end()); reverse(qr.begin(), qr.end()); for(auto [x, t, y, z, id]: qr) { if(t == 1) { ll pos = upper_bound(nen.begin(), nen.end(), y) - nen.begin(); up(pos, x + y, 1); } else { ll pos = upper_bound(nen.begin(), nen.end(), y) - nen.begin(); kq[id] = get(pos, nen.size(), z, (1ll << 32) - 1); } } fr(i, 1, q) cout<<kq[i]<<'\n'; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...