Submission #410424

#TimeUsernameProblemLanguageResultExecution timeMemory
410424JerryLiu06Examination (JOI19_examination)C++17
100 / 100
584 ms38620 KiB
#include <bits/stdc++.h> using namespace std; using ll = long long; using db = long double; using str = string; using pi = pair<int, int>; using pl = pair<ll, ll>; using pd = pair<db, db>; using vi = vector<int>; using vb = vector<bool>; using vl = vector<ll>; using vd = vector<db>; using vs = vector<str>; using vpi = vector<pi>; using vpl = vector<pl>; using vpd = vector<pd>; #define mp make_pair #define f first #define s second #define sz(x) (int)(x).size() #define bg(x) begin(x) #define all(x) bg(x), end(x) #define sor(x) sort(all(x)) #define ft front() #define bk back() #define pb push_back #define pf push_front #define lb lower_bound #define ub upper_bound #define FOR(i, a, b) for (int i = (a); i < (b); i++) #define F0R(i, a) FOR(i, 0, a) #define ROF(i, a, b) for (int i = (b) - 1; i >= (a); i--) #define R0F(i, a) ROF(i, 0, a) #define EACH(a, x) for (auto& a : x) const int MOD = 1e9 + 7; const int MX = 1e5 + 10; const ll INF = 1e18; template<class T, int SZ> struct BIT2D { bool mode = 0; vpi todo; int cnt[SZ], st[SZ]; vi val; vector<T> BIT; void init() { mode = 1; int lst[SZ]; F0R(i, SZ) lst[i] = cnt[i] = 0; sort(all(todo), [](const pi& A, const pi& B) { return A.s < B.s; }); EACH(P, todo) for (int x = P.f; x < SZ; x += (x & -x)) if (lst[x] != P.s) lst[x] = P.s, cnt[x]++; int sum = 0; F0R(i, SZ) lst[i] = 0, st[i] = (sum += cnt[i]); val.resize(sum); BIT.resize(sum); reverse(all(todo)); EACH(P, todo) for (int x = P.f; x < SZ; x += (x & -x)) if (lst[x] != P.s) lst[x] = P.s, val[--st[x]] = P.s; } int compress(int Y, int L, int R) { return ub(val.bg() + L, val.bg() + R, Y) - val.bg() - L; } void UPD(int X, int Y, T val) { for (Y = compress(Y, st[X], st[X] + cnt[X]); Y <= cnt[X]; Y += (Y & -Y)) BIT[st[X] + Y - 1] += val; } void upd(int X, int Y, T val) { if (mode == 0) { todo.pb({X, Y}); return ; } for ( ; X < SZ; X += (X & -X)) UPD(X, Y, val); } T QUERY(int X, int Y) { T res = 0; for (Y = compress(Y, st[X], st[X] + cnt[X]); Y > 0; Y -= (Y & -Y)) res += BIT[st[X] + Y - 1]; return res; } T query(int X, int Y) { T res = 0; for (; X > 0; X -= (X & -X)) res += QUERY(X, Y); return res; } T query(int xL, int xR, int yL, int yR) { return query(xR, yR) - query(xL - 1, yR) - query(xR, yL - 1) + query(xL - 1, yL - 1); } }; int N, Q; vl allY, allZ; vector<array<ll, 3>> A; vector<array<ll, 4>> B; BIT2D<ll, 2 * MX> BIT; int ans[MX]; int getY(int Y) { return ub(all(allY), Y) - allY.bg(); } int getZ(int Z) { return ub(all(allZ), Z) - allZ.bg(); } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> N >> Q; F0R(i, N) { ll X, Y; cin >> X >> Y; A.pb({X, Y, X + Y}); allY.pb(Y), allZ.pb(X + Y); } F0R(i, Q) { ll X, Y, Z; cin >> X >> Y >> Z; B.pb({X, Y, Z, i}); allY.pb(Y), allZ.pb(Z); } sort(all(allY)); sort(all(allZ)); allY.erase(unique(all(allY)), allY.end()); allZ.erase(unique(all(allZ)), allZ.end()); sort(all(A), [&](array<ll, 3> a, array<ll, 3> b) { return a[0] > b[0]; }); sort(all(B), [&](array<ll, 4> a, array<ll, 4> b) { return a[0] > b[0]; }); F0R(i, N) A[i][1] = getY(A[i][1]), A[i][2] = getZ(A[i][2]); F0R(i, Q) B[i][1] = getY(B[i][1]), B[i][2] = getZ(B[i][2]); F0R(i, N) BIT.upd(A[i][1], A[i][2], 1); BIT.init(); int ptr = 0; F0R(i, Q) { while (ptr < N && A[ptr][0] >= B[i][0]) { BIT.upd(A[ptr][1], A[ptr][2], 1); ptr++; } ans[B[i][3]] = BIT.query(B[i][1], 2 * MX, B[i][2], 2 * MX); } F0R(i, Q) cout << ans[i] << "\n"; }

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:38:22: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   38 | #define FOR(i, a, b) for (int i = (a); i < (b); i++)
      |                      ^~~
examination.cpp:39:19: note: in expansion of macro 'FOR'
   39 | #define F0R(i, a) FOR(i, 0, a)
      |                   ^~~
examination.cpp:100:5: note: in expansion of macro 'F0R'
  100 |     F0R(i, N) BIT.upd(A[i][1], A[i][2], 1); BIT.init();
      |     ^~~
examination.cpp:100:45: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  100 |     F0R(i, N) BIT.upd(A[i][1], A[i][2], 1); BIT.init();
      |                                             ^~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...