Submission #410424

#	Time	Username	Problem	Language	Result	Execution time	Memory
410424		JerryLiu06	Examination (JOI19_examination)	C++17	100 / 100	584 ms	38620 KiB

examination

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

• Subtask 1: 2 / 2
• Subtask 2: 20 / 20
• Subtask 3: 21 / 21
• Subtask 4: 57 / 57