oj.uz

Submission #202008

# Submission time Handle Problem Language Result Execution time Memory
202008 2020-02-13T03:21:54 Z _7_7_ Examination (JOI19_examination) C++14
100 / 100
 1704 ms 408140 KB 
#include <bits/stdc++.h>                                           
 
//#define int long long
//#pragma GCC optimize("Ofast")
//#pragma comment(linker, "/stack:200000000")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4")
 
 
#define file(s) freopen(s".in","r",stdin); freopen(s".out","w",stdout);
#define forev(i, b, a) for(int i = (b); i >= (a); --i)
#define forn(i, a, b) for(int i = (a); i <= (b); ++i)
#define all(x) x.begin(), x.end()
#define sz(s) (int)s.size()
#define pb push_back
#define ppb pop_back
#define mp make_pair
#define s second
#define f first
 
 
using namespace std;
 
 
typedef pair < long long, long long > pll;    
typedef pair < int, int > pii;
typedef unsigned long long ull;         
typedef vector < pii > vpii;
typedef vector < int > vi;
typedef long double ldb;  
typedef long long ll;  
typedef double db;                             
 
 
const int dx[] = {1, -1, 0, 0}, dy[] = {0, 0, 1, -1}, block = 333;
const pii base = mp(1171, 3307), Mod = mp(1e9 + 7, 1e9 + 9);
const int inf = 1e9, maxn = 4e5 + 148, mod = 1e9 + 7, N = 1e5 + 11;
const db eps = 1e-12, pi = 3.14159265359;
const ll INF = 1e18;

inline int R () {
	char c;
	bool is_negative = 0, started = 0;
	int ans = 0;
	while (1) {
		c = getchar();
		if ((c > '9' || c < '0') && c != '-' && !started)
			continue;
		if ((c > '9' || c < '0') && c != '-' && started)
			break;
		started = 1;
		if (c == '-')
			is_negative = 1;
		else
			ans = ans * 10 + c - '0';
	}

	return ans;
}

int n, q, X[N], Y[N], res[N];


struct node {
	int x, y;
	bool operator < (const node &a) const {	
		return X[x] + Y[y] > X[a.x] + Y[a.y];
	}	
} d[N];

struct query {
	int a, b, c, id;
	bool operator < (const query &x) const {
		return c > x.c;
	}
} e[N];

struct ST {
	int tl, tr;
	ST *l, *r;
	int sum;

	ST () {}
	
	ST (int a, int b) {
		tl = a;
		tr = b;	
		sum = 0;
		l = r = NULL;
	}

	void update (int pos, int x) {
		if (tl == tr) {
			sum += x;
			return;
		}	
		int tm = (tl + tr) >> 1;
		if (pos <= tm) {
			if (!l)
				l = new ST(tl, tm);
			l->update(pos, x);
		} else {
			if (!r)
				r = new ST(tm + 1, tr);
			r->update(pos, x);
		}

		sum = (!l ? 0 : l->sum) + (!r ? 0 : r->sum);
	}

	int get (int lf, int rg) {
		if (lf > rg || tl > rg || lf > tr)	
			return 0;
		if (lf <= tl && tr <= rg)
			return sum;
		return (l ? l->get(lf, rg) : 0) + (r ? r->get(lf, rg) : 0);
	}

};

struct BIT {
	ST *T[N];
	
	BIT () {
		memset(T, 0, sizeof(T));
	}

	void add (int x, int y, int z) {
		x = N - 1 - x;
		while (x < N) {
			if (!T[x])
				T[x] = new ST(0, N - 1);				
			T[x]->update(y, z);
			x += x & -x;
		}	
	}

	int get (int x, int y) {
		x = N - 1 - x;
	    int res = 0;
		while (x > 0) {
			if (T[x]) 
				res += T[x]->get(y, N - 1);
			x -= x & -x;
		}	
		return res;
	}
} F;





main () {
//	file("");
	n = R(), q = R();
	forn (i, 1, n) {
		d[i].x = R();
		d[i].y = R();
		X[i] = d[i].x;
		Y[i] = d[i].y;
	}

	sort(X + 1, X + 1 + n);
	sort(Y + 1, Y + 1 + n);

	forn (i, 1, n) {
		d[i].x = lower_bound(X + 1, X + 1 + n, d[i].x) - X;
		d[i].y = lower_bound(Y + 1, Y + 1 + n, d[i].y) - Y;
	}



	forn (i, 1, q) {
		e[i].a = R(); 
		e[i].b = R();	
		e[i].c = R();
		e[i].id = i;
		e[i].a = lower_bound(X + 1, X + 1 + n, e[i].a) - X;
		e[i].b = lower_bound(Y + 1, Y + 1 + n, e[i].b) - Y;
	}

	sort(d + 1, d + 1 + n);
	sort(e + 1, e + 1 + q);

	int j = 1;
	forn (i, 1, q) {
		while (j <= n && X[d[j].x] + Y[d[j].y] >= e[i].c) {
			F.add(d[j].x, d[j].y, 1);
//			cerr << " + " << d[j].x << ' ' << d[j].y << endl;
			++j;
		}
//		cerr << e[i].a << ' ' << e[i].b << " = " << get(e[i].a, e[i].b) << endl;
		res[e[i].id] = F.get(e[i].a, e[i].b);
	}

	forn (i, 1, q)
		printf("%d\n", res[i]);
}

Compilation message

examination.cpp: In function 'int R()':
examination.cpp:42:7: warning: variable 'is_negative' set but not used [-Wunused-but-set-variable]
  bool is_negative = 0, started = 0;
       ^~~~~~~~~~~
examination.cpp: At global scope:
examination.cpp:153:7: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main () {
       ^

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1144 KB Output is correct
2 Correct 5 ms 1144 KB Output is correct
3 Correct 5 ms 1148 KB Output is correct
4 Correct 5 ms 1144 KB Output is correct
5 Correct 5 ms 1144 KB Output is correct
6 Correct 5 ms 1144 KB Output is correct
7 Correct 22 ms 8056 KB Output is correct
8 Correct 22 ms 8184 KB Output is correct
9 Correct 22 ms 8184 KB Output is correct
10 Correct 19 ms 5752 KB Output is correct
11 Correct 16 ms 4984 KB Output is correct
12 Correct 9 ms 1528 KB Output is correct
13 Correct 23 ms 8184 KB Output is correct
14 Correct 23 ms 8184 KB Output is correct
15 Correct 24 ms 8184 KB Output is correct
16 Correct 9 ms 1784 KB Output is correct
17 Correct 13 ms 3704 KB Output is correct
18 Correct 7 ms 1272 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1704 ms 398572 KB Output is correct
2 Correct 1634 ms 400528 KB Output is correct
3 Correct 1627 ms 400312 KB Output is correct
4 Correct 703 ms 184956 KB Output is correct
5 Correct 631 ms 173048 KB Output is correct
6 Correct 153 ms 6776 KB Output is correct
7 Correct 1506 ms 400888 KB Output is correct
8 Correct 1525 ms 400844 KB Output is correct
9 Correct 1229 ms 400204 KB Output is correct
10 Correct 165 ms 21624 KB Output is correct
11 Correct 339 ms 73560 KB Output is correct
12 Correct 58 ms 5880 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1704 ms 398572 KB Output is correct
2 Correct 1634 ms 400528 KB Output is correct
3 Correct 1627 ms 400312 KB Output is correct
4 Correct 703 ms 184956 KB Output is correct
5 Correct 631 ms 173048 KB Output is correct
6 Correct 153 ms 6776 KB Output is correct
7 Correct 1506 ms 400888 KB Output is correct
8 Correct 1525 ms 400844 KB Output is correct
9 Correct 1229 ms 400204 KB Output is correct
10 Correct 165 ms 21624 KB Output is correct
11 Correct 339 ms 73560 KB Output is correct
12 Correct 58 ms 5880 KB Output is correct
13 Correct 1371 ms 401084 KB Output is correct
14 Correct 1613 ms 401016 KB Output is correct
15 Correct 1618 ms 400656 KB Output is correct
16 Correct 559 ms 186492 KB Output is correct
17 Correct 522 ms 162552 KB Output is correct
18 Correct 157 ms 6904 KB Output is correct
19 Correct 1385 ms 400760 KB Output is correct
20 Correct 1477 ms 401656 KB Output is correct
21 Correct 1192 ms 401384 KB Output is correct
22 Correct 157 ms 21752 KB Output is correct
23 Correct 350 ms 73464 KB Output is correct
24 Correct 63 ms 5880 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 1144 KB Output is correct
2 Correct 5 ms 1144 KB Output is correct
3 Correct 5 ms 1148 KB Output is correct
4 Correct 5 ms 1144 KB Output is correct
5 Correct 5 ms 1144 KB Output is correct
6 Correct 5 ms 1144 KB Output is correct
7 Correct 22 ms 8056 KB Output is correct
8 Correct 22 ms 8184 KB Output is correct
9 Correct 22 ms 8184 KB Output is correct
10 Correct 19 ms 5752 KB Output is correct
11 Correct 16 ms 4984 KB Output is correct
12 Correct 9 ms 1528 KB Output is correct
13 Correct 23 ms 8184 KB Output is correct
14 Correct 23 ms 8184 KB Output is correct
15 Correct 24 ms 8184 KB Output is correct
16 Correct 9 ms 1784 KB Output is correct
17 Correct 13 ms 3704 KB Output is correct
18 Correct 7 ms 1272 KB Output is correct
19 Correct 1704 ms 398572 KB Output is correct
20 Correct 1634 ms 400528 KB Output is correct
21 Correct 1627 ms 400312 KB Output is correct
22 Correct 703 ms 184956 KB Output is correct
23 Correct 631 ms 173048 KB Output is correct
24 Correct 153 ms 6776 KB Output is correct
25 Correct 1506 ms 400888 KB Output is correct
26 Correct 1525 ms 400844 KB Output is correct
27 Correct 1229 ms 400204 KB Output is correct
28 Correct 165 ms 21624 KB Output is correct
29 Correct 339 ms 73560 KB Output is correct
30 Correct 58 ms 5880 KB Output is correct
31 Correct 1371 ms 401084 KB Output is correct
32 Correct 1613 ms 401016 KB Output is correct
33 Correct 1618 ms 400656 KB Output is correct
34 Correct 559 ms 186492 KB Output is correct
35 Correct 522 ms 162552 KB Output is correct
36 Correct 157 ms 6904 KB Output is correct
37 Correct 1385 ms 400760 KB Output is correct
38 Correct 1477 ms 401656 KB Output is correct
39 Correct 1192 ms 401384 KB Output is correct
40 Correct 157 ms 21752 KB Output is correct
41 Correct 350 ms 73464 KB Output is correct
42 Correct 63 ms 5880 KB Output is correct
43 Correct 1398 ms 408140 KB Output is correct
44 Correct 1393 ms 408056 KB Output is correct
45 Correct 1629 ms 408056 KB Output is correct
46 Correct 594 ms 190584 KB Output is correct
47 Correct 586 ms 194680 KB Output is correct
48 Correct 142 ms 6648 KB Output is correct
49 Correct 1392 ms 407968 KB Output is correct
50 Correct 1204 ms 408056 KB Output is correct
51 Correct 1112 ms 407756 KB Output is correct
52 Correct 181 ms 27128 KB Output is correct
53 Correct 368 ms 92024 KB Output is correct