Submission #1116605

#TimeUsernameProblemLanguageResultExecution timeMemory
1116605gdragonExamination (JOI19_examination)C++17
100 / 100
486 ms34664 KiB
#include <bits/stdc++.h> using namespace std; #define TASK "long" #define fi first #define se second #define ll long long #define pb push_back #define ALL(x) (x).begin(), (x).end() #define GETBIT(mask, i) ((mask) >> (i) & 1) #define MASK(i) ((1LL) << (i)) #define SZ(x) ((int)(x).size()) #define mp make_pair #define CNTBIT(mask) __builtin_popcount(mask) template<class X, class Y> bool maximize(X &x, Y y){ if (x < y) {x = y; return true;} return false;}; template<class X, class Y> bool minimize(X &x, Y y){ if (x > y) {x = y; return true;} return false;}; typedef pair<int, int> ii; const int N = 1e5 + 100; const int INF = 2e9 + 7; const int mod = 1e9 + 7; struct BIT2d { int n, m; vector<vector<int>> nodes, f; BIT2d(int _n = 0) { n = _n; nodes.assign(n + 2, vector<int>()); f.assign(n + 2, vector<int>()); } void fakeUpdate(int x, int y) { for(; x <= n; x += x & -x) nodes[x].push_back(y); } void init() { for(int i = 1; i <= n; i++) { nodes[i].push_back(INF); sort(ALL(nodes[i])); nodes[i].erase(unique(ALL(nodes[i])), nodes[i].end()); f[i].assign(SZ(nodes[i]) + 1, 0); } } void update(int x, int y, int val) { for(int i = x; i <= n; i += i & -i) { for(int j = lower_bound(ALL(nodes[i]), y) - nodes[i].begin() + 1; j <= SZ(nodes[i]); j += j & -j) { f[i][j] += val; } } } int get(int x, int y) { int ans = 0; for(int i = x; i > 0; i -= i & -i) { for(int j = upper_bound(ALL(nodes[i]), y) - nodes[i].begin(); j > 0; j -= j & -j) { ans += f[i][j]; } } return ans; } } fw; struct Fenwick { int n; vector<int> v; Fenwick(int _n = 0) { n = _n; v.assign(n + 5, 0); } void update(int x, int c) { for(; x > 0; x -= x & -x) v[x] += c; } int get(int x) { int ans = 0; for(; x <= n; x += x & -x) ans += v[x]; return ans; } } fw1, fw2; struct Query { int x, y; int type; int id; Query(int _x = 0, int _y = 0, int _type = 0, int _id = 0) { x = _x; y = _y; type = _type; id = _id; } }; int n, q; int ans[N]; pair<int, int> a[N]; vector<pair<int, pair<int, int>>> queries[N]; void read() { cin >> n >> q; for(int i = 1; i <= n; i++) cin >> a[i].fi >> a[i].se; } vector<int> valB, valC; void compress() { for(int i = 1; i <= n; i++) { valB.push_back(a[i].se); valC.push_back(a[i].fi + a[i].se); } valB.push_back(INF); valC.push_back(INF); sort(ALL(valB)); valB.erase(unique(ALL(valB)), valB.end()); sort(ALL(valC)); valC.erase(unique(ALL(valC)), valC.end()); // cerr << SZ(valB) << ' ' << SZ(valC) << endl; } void solve() { sort(a + 1, a + n + 1); for(int i = 1; i <= q; i++) { int A, B, C; cin >> A >> B >> C; int p = lower_bound(a + 1, a + n + 1, mp(A, 0)) - a; // cerr << p << endl; if (p > n) ans[i] = 0; else { queries[p].push_back({i, mp(B, C)}); } } compress(); fw1 = Fenwick(SZ(valB)); fw2 = Fenwick(SZ(valC)); vector<Query> gdragon; for(int i = n; i >= 1; i--) { int b = lower_bound(ALL(valB), a[i].se) - valB.begin() + 1; fw1.update(b, 1); int c = lower_bound(ALL(valC), a[i].fi + a[i].se) - valC.begin() + 1; fw2.update(c, 1); // update(b, c, 1); gdragon.push_back(Query(b, c, 0)); // cerr << "BC: " << b << ' ' << c << endl; for(auto &query: queries[i]) { int id = query.fi; int B = query.se.fi; int C = query.se.se; B = lower_bound(ALL(valB), B) - valB.begin() + 1; C = lower_bound(ALL(valC), C) - valC.begin() + 1; // cerr << id << ' ' << B << ' ' << query.se.fi << ' ' << C << ' ' << query.se.se << endl; ans[id] = fw1.get(B) + fw2.get(C) - (n - i + 1); gdragon.push_back(Query(B - 1, C - 1, 1, id)); // cerr << id << ' ' << ans[id] << endl; // ans[id] += get(B - 1, C - 1); // for(int j = i; j <= n; j++) if (a[j].se < query.se.fi && a[j].fi + a[j].se < query.se.se) { // ++ans[id]; // } } } fw = BIT2d(SZ(valB)); for(auto &i: gdragon) { if (i.type == 0) fw.fakeUpdate(i.x, i.y); } fw.init(); for(auto &i: gdragon) { if (!i.type) fw.update(i.x, i.y, 1); else ans[i.id] += fw.get(i.x, i.y); } for(int i = 1; i <= q; i++) cout << ans[i] << endl; } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if (fopen(TASK".inp", "r")) { freopen(TASK".inp", "r", stdin); freopen(TASK".out", "w", stdout); } int test = 1; // cin >> test; while(test--) { read(); solve(); } return 0; }

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:156:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  156 |         freopen(TASK".inp", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:157:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |         freopen(TASK".out", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...