oj.uz

Submission #410424

# Submission time Handle Problem Language Result Execution time Memory
410424 2021-05-22T16:48:14 Z JerryLiu06 Examination (JOI19_examination) C++17
100 / 100
 584 ms 38620 KB 
#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

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();
      |                                             ^~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2716 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2632 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 12 ms 3660 KB Output is correct
8 Correct 12 ms 3668 KB Output is correct
9 Correct 12 ms 3660 KB Output is correct
10 Correct 10 ms 3788 KB Output is correct
11 Correct 11 ms 3580 KB Output is correct
12 Correct 6 ms 3148 KB Output is correct
13 Correct 11 ms 3672 KB Output is correct
14 Correct 11 ms 3568 KB Output is correct
15 Correct 11 ms 3660 KB Output is correct
16 Correct 10 ms 3624 KB Output is correct
17 Correct 9 ms 3800 KB Output is correct
18 Correct 5 ms 3148 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 28640 KB Output is correct
2 Correct 435 ms 28564 KB Output is correct
3 Correct 409 ms 28512 KB Output is correct
4 Correct 241 ms 29588 KB Output is correct
5 Correct 384 ms 24812 KB Output is correct
6 Correct 132 ms 16064 KB Output is correct
7 Correct 400 ms 28776 KB Output is correct
8 Correct 365 ms 28384 KB Output is correct
9 Correct 355 ms 28312 KB Output is correct
10 Correct 374 ms 24128 KB Output is correct
11 Correct 217 ms 30172 KB Output is correct
12 Correct 108 ms 15648 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 415 ms 28640 KB Output is correct
2 Correct 435 ms 28564 KB Output is correct
3 Correct 409 ms 28512 KB Output is correct
4 Correct 241 ms 29588 KB Output is correct
5 Correct 384 ms 24812 KB Output is correct
6 Correct 132 ms 16064 KB Output is correct
7 Correct 400 ms 28776 KB Output is correct
8 Correct 365 ms 28384 KB Output is correct
9 Correct 355 ms 28312 KB Output is correct
10 Correct 374 ms 24128 KB Output is correct
11 Correct 217 ms 30172 KB Output is correct
12 Correct 108 ms 15648 KB Output is correct
13 Correct 520 ms 29096 KB Output is correct
14 Correct 497 ms 28924 KB Output is correct
15 Correct 409 ms 28600 KB Output is correct
16 Correct 304 ms 30148 KB Output is correct
17 Correct 450 ms 25268 KB Output is correct
18 Correct 144 ms 16092 KB Output is correct
19 Correct 507 ms 28972 KB Output is correct
20 Correct 529 ms 29072 KB Output is correct
21 Correct 465 ms 29044 KB Output is correct
22 Correct 362 ms 24172 KB Output is correct
23 Correct 220 ms 29972 KB Output is correct
24 Correct 108 ms 15652 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2716 KB Output is correct
2 Correct 2 ms 2636 KB Output is correct
3 Correct 2 ms 2636 KB Output is correct
4 Correct 2 ms 2632 KB Output is correct
5 Correct 2 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 12 ms 3660 KB Output is correct
8 Correct 12 ms 3668 KB Output is correct
9 Correct 12 ms 3660 KB Output is correct
10 Correct 10 ms 3788 KB Output is correct
11 Correct 11 ms 3580 KB Output is correct
12 Correct 6 ms 3148 KB Output is correct
13 Correct 11 ms 3672 KB Output is correct
14 Correct 11 ms 3568 KB Output is correct
15 Correct 11 ms 3660 KB Output is correct
16 Correct 10 ms 3624 KB Output is correct
17 Correct 9 ms 3800 KB Output is correct
18 Correct 5 ms 3148 KB Output is correct
19 Correct 415 ms 28640 KB Output is correct
20 Correct 435 ms 28564 KB Output is correct
21 Correct 409 ms 28512 KB Output is correct
22 Correct 241 ms 29588 KB Output is correct
23 Correct 384 ms 24812 KB Output is correct
24 Correct 132 ms 16064 KB Output is correct
25 Correct 400 ms 28776 KB Output is correct
26 Correct 365 ms 28384 KB Output is correct
27 Correct 355 ms 28312 KB Output is correct
28 Correct 374 ms 24128 KB Output is correct
29 Correct 217 ms 30172 KB Output is correct
30 Correct 108 ms 15648 KB Output is correct
31 Correct 520 ms 29096 KB Output is correct
32 Correct 497 ms 28924 KB Output is correct
33 Correct 409 ms 28600 KB Output is correct
34 Correct 304 ms 30148 KB Output is correct
35 Correct 450 ms 25268 KB Output is correct
36 Correct 144 ms 16092 KB Output is correct
37 Correct 507 ms 28972 KB Output is correct
38 Correct 529 ms 29072 KB Output is correct
39 Correct 465 ms 29044 KB Output is correct
40 Correct 362 ms 24172 KB Output is correct
41 Correct 220 ms 29972 KB Output is correct
42 Correct 108 ms 15652 KB Output is correct
43 Correct 584 ms 30868 KB Output is correct
44 Correct 553 ms 30848 KB Output is correct
45 Correct 525 ms 30748 KB Output is correct
46 Correct 328 ms 37728 KB Output is correct
47 Correct 501 ms 29264 KB Output is correct
48 Correct 144 ms 15964 KB Output is correct
49 Correct 500 ms 30688 KB Output is correct
50 Correct 476 ms 30280 KB Output is correct
51 Correct 437 ms 30084 KB Output is correct
52 Correct 506 ms 29072 KB Output is correct
53 Correct 233 ms 38620 KB Output is correct