Submission #927823

#TimeUsernameProblemLanguageResultExecution timeMemory
927823hqminhuwuExamination (JOI19_examination)C++14
100 / 100
1536 ms28312 KiB
#include <bits/stdc++.h> #define forr(_a,_b,_c) for(_a = (_b); _a <= (_c); ++_a) #define ford(_a,_b,_c) for(_a = (_b) + 1; _a --> (_c);) #define forf(_a,_b,_c) for(_a = (_b); _a < (_c); ++_a) #define st first #define nd second #define ll long long #define ull unsigned long long #define pii pair <int,int> #define pll pair <ll,ll> #define piii pair <int,pii> #define vi vector <int> #define pb push_back #define mp make_pair #define all(x) begin(x),end(x) #define file "test" using namespace std; const int N = 5e5 + 5; const ll oo = 1e9; const ll mod = 1e9 + 7; const int uwu = 317; pair <pii, pii> w[N]; int bit[uwu + 5][uwu + 5], n, q, i, j, k, ans[N], flag[N]; pii a[N]; vector <pii> f; vi v[N]; void update (int id, int x){ for (; x > 0; x -= x & -x) bit[id][x]++; } int get (int id, int x){ int res = 0; for (; x <= uwu + 1; x += x & -x) res += bit[id][x]; return res; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); #ifdef hqm freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout); #endif cin >> n >> q; forr (i, 1, n) cin >> a[i].st >> a[i].nd; sort(a + 1, a + 1+ n); forr (i, 1, n) f.pb({a[i].st + a[i].nd, i}); forr (i, 1, n) v[i / uwu].pb(a[i].nd); forr (i, 0, n / uwu){ sort(all(v[i])), v[i].erase(unique(all(v[i])), v[i].end()); } forr (i, 1, q) cin >> w[i].nd.st >> w[i].nd.nd >> w[i].st.st, w[i].st.nd = i; sort(w + 1, w + 1 + n, greater<pair<pii, pii>>()); sort(all(f)); int it = f.size() - 1; forr (i, 1, q){ int z = w[i].st.st, x = w[i].nd.st, y = w[i].nd.nd, pos = w[i].st.nd; while (it >= 0 && f[it].st >= z){ int id = f[it].nd / uwu; flag[f[it].nd] = 1; int tmp = lower_bound(all(v[id]), a[f[it].nd].nd) - v[id].begin() + 1; //cout << f[it].st << " " << a[f[it].nd].st << " " << a[f[it].nd].nd << " " << id << " " << tmp << "\n"; update(id, tmp); it--; } int j = n / uwu; while (j >= 0 && a[uwu * j].st >= x){ int e = lower_bound(all(v[j]), y) - v[j].begin() + 1; // cout << e << "\n"; ans[pos] += get(j, e); j--; } if (j >= 0) ford (k, uwu * (j + 1) - 1, j * uwu){ ans[pos] += (y <= a[k].nd && x <= a[k].st) * flag[k]; } // cout << y << "\n"; } forr (i, 1, q) cout << ans[i] << "\n"; return 0; } /* */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...