Submission #1274282

#TimeUsernameProblemLanguageResultExecution timeMemory
1274282nanaseyuzukiExamination (JOI19_examination)C++20
0 / 100
119 ms12020 KiB
#include <bits/stdc++.h> // Author: Kazuki_Will_Win_VOI_8703 #define fi first #define se second #define pii pair<int, int> #define int long long #define all(a) a.begin(), a.end() using namespace std; const int mn = 5e5 + 5, bm = (1 << 11) + 1, mod = 1e9 + 7, offset = 5e4, B = 320 + 5; const int inf = 1e9, base = 311; int n, q, ans[mn]; struct Megumi{ int s, t, c; bool operator<(const Megumi& other){ return c > other.c; } } e[mn]; struct Reina{ int a, b, c, id; bool operator<(const Reina& other){ return c > other.c; } } qr[mn]; int bit[2][mn]; void add(int t, int u, int val){ while(u <= 3e5){ bit[t][u] += val; u += (u & -u); } } int get(int t, int u){ int res = 0; while(u){ res += bit[t][u]; u -= (u & -u); } return res; } signed main(){ ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> n >> q; vector <int> comp1, comp2; for(int i = 1; i <= n; i++){ cin >> e[i].s >> e[i].t; e[i].c = e[i].s + e[i].t; comp1.push_back(e[i].s); comp2.push_back(e[i].t); } sort(e + 1, e + n + 1); for(int i = 1; i <= q; i++){ cin >> qr[i].a >> qr[i].b >> qr[i].c; qr[i].c = max(qr[i].c, qr[i].a + qr[i].b); qr[i].id = i; comp1.push_back(qr[i].a); comp2.push_back(qr[i].b); } sort(all(comp1)); comp1.erase(unique(all(comp1)), comp1.end()); sort(all(comp2)); comp2.erase(unique(all(comp2)), comp2.end()); sort(qr + 1, qr + q + 1); int ptr = 1, cnt = 0; for(int i = 1; i <= q; i++){ while(ptr <= n && e[ptr].c >= qr[i].c){ int id1 = lower_bound(comp1.begin(), comp1.end(), e[ptr].s) - comp1.begin() + 1; add(0, id1, 1); int id2 = lower_bound(comp2.begin(), comp2.end(), e[ptr].t) - comp2.begin() + 1; add(1, id2, 1); ptr ++, cnt ++; } int id1 = upper_bound(comp1.begin(), comp1.end(), qr[i].a) - comp1.begin(); int id2 = upper_bound(comp2.begin(), comp2.end(), qr[i].b) - comp2.begin(); ans[qr[i].id] = cnt - get(0, id1) - get(1, id2); } for(int i = 1; i <= q; i++) cout << ans[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...