Submission #124634

#	Time	Username	Problem	Language	Result	Execution time	Memory
124634		antimirage	Examination (JOI19_examination)	C++14	100 / 100	426 ms	39544 KiB

examination

/** 
	MAYBE THERE'S ONLY A DARK ROAD UP AHEAD.
	BUT YOU still HAVE TO BELIEVE AND KEEP GOING.
	BELIEVE THAT THE STARS WILL LIGHT YOUR PATH,
	EVEN A LITTLE BIT. COME ON...
	LET'S go on A JOURNEY! 
**/
#include <bits/stdc++.h>
 
#define fr first
#define sc second
#define mk make_pair
#define pb push_back
#define all(s) s.begin(), s.end()
 
using namespace std;

const int N = 1e5 + 5;

int n, m, ans[N], inf = 1e9, sz[2] = {1, 1};

struct asd {
	int x, y, z, in;
};

asd a[N], b[N];

struct tree {
	int l, r, val;
};

tree t[2][N * 30];

void update (int ad, int pos, int v = 1, int tl = 0, int tr = inf) {
	if (tl == tr)
		t[ad][v].val++;
	else {
		int tm = (tl + tr) >> 1;
		if (pos <= tm) {
			if (!t[ad][v].l) t[ad][v].l = ++sz[ad];
			update(ad, pos, t[ad][v].l, tl, tm);
		}
		else {
			if (!t[ad][v].r) t[ad][v].r = ++sz[ad];
			update(ad, pos, t[ad][v].r, tm + 1, tr);
		}
		t[ad][v].val = t[ad][ t[ad][v].l ].val + t[ad][ t[ad][v].r ].val;
	}
}

bool cmp (asd x, asd y) {
	return x.z > y.z;
}
int get (int ad, int l, int r, int v = 1, int tl = 0, int tr = inf) {
	if (l > r || tl > r || l > tr || v == 0) 
		return 0;
		
	if (l <= tl && tr <= r)
		return t[ad][v].val;
		
	int tm = (tl + tr) >> 1;
	
	return get( ad, l, r, t[ad][v].l, tl, tm ) + get( ad, l, r, t[ad][v].r, tm + 1, tr );
}
main(){
	cin >> n >> m;
	
	for (int i = 1; i <= n; i++) {
		scanf("%d%d", &a[i].x, &a[i].y);
		a[i].z = a[i].x + a[i].y;
	}
	for (int i = 1; i <= m; i++) {
		scanf("%d%d%d", &b[i].x, &b[i].y, &b[i].z);
		b[i].z = max( b[i].z, b[i].x + b[i].y );
		b[i].in = i;
	}
	sort(a + 1, a + n + 1, cmp);
	sort(b + 1, b + m + 1, cmp);

	int j = 1;
	for (int i = 1; i <= m; i++) {
		while (j <= n && a[j].z >= b[i].z) {
			update(0, a[j].x);
			update(1, a[j].y);
			j++;
		}
		//cout << b[i].z << " " << get(1, 0, b[i].y - 1) << endl;
		ans[b[i].in] = j - get(0, 0, b[i].x - 1) - get(1, 0, b[i].y - 1) - 1;
	}
	for (int i = 1; i <= m; i++) {
		printf("%d\n", ans[i]);
	}
}

Compilation message (stderr)

examination.cpp:65:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^
examination.cpp: In function 'int main()':
examination.cpp:69:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &a[i].x, &a[i].y);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~
examination.cpp:73:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d", &b[i].x, &b[i].y, &b[i].z);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

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