Submission #102084

#	Time	Username	Problem	Language	Result	Execution time	Memory
102084		ainta	Examination (JOI19_examination)	C++17	100 / 100	1156 ms	45768 KiB

examination

#include<cstdio>
#include<algorithm>
#include<vector>
#define SZ 131072
using namespace std;
int n;
struct Query {
	int a, b, c, num;
	bool operator<(const Query &p)const {
		return c < p.c;
	}
}w[101000], U[101000];
int A[201000], B[201000], CA, CB, Res[101000];
struct IT2D {
	vector<int>V[SZ + SZ];
	vector<int>BIT[SZ + SZ];
	void Build(int nd, int b, int e) {
		V[nd].resize(e - b + 1);
		BIT[nd].resize(e - b + 2);
		for (int i = b; i <= e; i++) {
			V[nd][i - b] = w[i].b;
		}
		sort(V[nd].begin(), V[nd].end());
		if (b == e)return;
		int m = (b + e) >> 1;
		Build(nd * 2, b, m);
		Build(nd * 2 + 1, m + 1, e);
	}

	void Put2(int nd, int y) {
		int x = lower_bound(V[nd].begin(), V[nd].end(), y) - V[nd].begin();
		x++;
		int sz = V[nd].size();
		while (x <= sz) {
			BIT[nd][x]++;
			x += (x&-x);
		}
	}
	void Put(int nd, int b, int e, int x, int y) {
		Put2(nd, y);
		if (b == e) {
			return;
		}
		int m = (b + e) >> 1;
		if (x <= m)Put(nd * 2, b, m, x, y);
		else Put(nd * 2 + 1, m + 1, e, x, y);
	}
	int Sum(int nd, int x) {
		int r = 0;
		while (x) {
			r += BIT[nd][x];
			x -= (x&-x);
		}
		return r;
	}
	int Get2(int nd, int y) {
		int x = lower_bound(V[nd].begin(), V[nd].end(), y) - V[nd].begin();
		int sz = V[nd].size();
		return Sum(nd, sz) - Sum(nd, x);
	}
	int Get(int nd, int b, int e, int s, int l, int y) {
		if (s > l)return 0;
		if (b == s && e == l) {
			return Get2(nd, y);
		}
		int m = (b + e) >> 1, r = 0;
		if (s <= m)r += Get(nd * 2, b, m, s, min(m, l), y);
		if (l > m)r += Get(nd * 2 + 1, m + 1, e, max(m + 1, s), l, y);
		return r;
	}
}TT;
int main() {
	int i, Q;
	scanf("%d%d", &n, &Q);
	for (i = 1; i <= n; i++) {
		scanf("%d%d", &w[i].a, &w[i].b);
		w[i].c = w[i].a + w[i].b;
		A[++CA] = w[i].a;
		B[++CB] = w[i].b;
	}
	for (i = 1; i <= Q; i++) {
		scanf("%d%d%d", &U[i].a, &U[i].b, &U[i].c);
		U[i].num = i;
	}
	sort(A + 1, A + CA + 1);
	sort(B + 1, B + CB + 1);
	for (i = 1; i <= n; i++) {
		w[i].a = lower_bound(A + 1, A + CA + 1, w[i].a) - A;
		w[i].b = lower_bound(B + 1, B + CB + 1, w[i].b) - B;
	}
	for (i = 1; i <= Q; i++) {
		U[i].a = lower_bound(A + 1, A + CA + 1, U[i].a) - A;
		U[i].b = lower_bound(B + 1, B + CB + 1, U[i].b) - B;
	}
	for (i = 1; i <= n; i++) {
		swap(w[i].a, w[i].c);
	}
	sort(w + 1, w + n + 1);
	for (i = 1; i <= n; i++) {
		swap(w[i].a, w[i].c);
		w[i].num = i;
		w[i].a = i;
	}
	TT.Build(1, 1, n);
	sort(w + 1, w + n + 1);
	sort(U + 1, U + Q + 1);
	int pv = n;
	for (i = Q; i >= 1; i--) {
		while (pv >= 1 && w[pv].c >= U[i].c) {
			TT.Put(1, 1, n, w[pv].a, w[pv].b);
			pv--;
		}
		Res[U[i].num] = TT.Get(1, 1, n, U[i].a, n, U[i].b);
	}
	for (i = 1; i <= Q; i++)printf("%d\n", Res[i]);
}

Compilation message (stderr)

examination.cpp: In function 'int main()':
examination.cpp:74:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &Q);
  ~~~~~^~~~~~~~~~~~~~~~
examination.cpp:76:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &w[i].a, &w[i].b);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &U[i].a, &U[i].b, &U[i].c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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