Submission #702416

#TimeUsernameProblemLanguageResultExecution timeMemory
702416PixelCatExamination (JOI19_examination)C++14
20 / 100
3080 ms65548 KiB
#include <bits/stdc++.h> #define For(i, a, b) for(int i = a; i <= b; i++) #define Forr(i, a, b) for(int i = a; i >= b; i--) #define F first #define S second #define all(x) x.begin(), x.end() #define sz(x) ((int)x.size()) #define eb emplace_back #define int LL using namespace std; using LL = long long; using pii = pair<int, int>; const int MAXN = 100010; #define L(id) (id * 2 + 1) #define R(id) (id * 2 + 2) struct SegTree { vector<int> st[MAXN << 2], t[MAXN << 2]; void build(int id, int l, int r, vector<int> &vs, vector<vector<int>> &vt) { For(it, l, r) for(auto &j:vt[it]) { t[id].eb(j); st[id].eb(vs[it] + j); } sort(all(t[id])); sort(all(st[id])); if(l == r) return; int m = (l + r) / 2; build(L(id), l, m, vs, vt); build(R(id), m + 1, r, vs, vt); } int count(const vector<int> &v, int x) { return v.end() - lower_bound(all(v), x); } int ask(int id, int l, int r, int L, int R, int type, int x) { if(l >= L && r <= R) { if(type) return count(t[id], x); return count(st[id], x); } int m = (l + r) / 2; if(R <= m) return ask(L(id), l, m, L, R, type, x); if(L > m) return ask(R(id), m + 1, r, L, R, type, x); return ask(L(id), l, m, L, R, type, x) + ask(R(id), m + 1, r, L, R, type, x); } } seg; int32_t main() { ios::sync_with_stdio(false); cin.tie(0); // nyanyanyanyanya int n, q; cin >> n >> q; vector<pii> pts; vector<int> vs; For(i, 1, n) { int s, t; cin >> s >> t; pts.eb(s, t); vs.eb(s); } sort(all(vs)); vs.erase(unique(all(vs)), vs.end()); int m = sz(vs); vector<vector<int>> vt(m); for(auto &p:pts) { int it = lower_bound(all(vs), p.F) - vs.begin(); vt[it].eb(p.S); } seg.build(0, 0, m - 1, vs, vt); while(q--) { int a, b, c; cin >> a >> b >> c; int res; if(a + b >= c) { int p = lower_bound(all(vs), a) - vs.begin(); res = seg.ask(0, 0, m - 1, p, m, 1, b); } else { int p1 = lower_bound(all(vs), a) - vs.begin(); int p2 = lower_bound(all(vs), c - b) - vs.begin(); res = seg.ask(0, 0, m - 1, p1, p2 - 1, 0, c) + seg.ask(0, 0, m - 1, p2, m, 1, b); } cout << res << "\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...