oj.uz

Submission #202009

# Submission time Handle Problem Language Result Execution time Memory
202009 2020-02-13T03:24:50 Z _7_7_ Examination (JOI19_examination) C++14
100 / 100
 1636 ms 403536 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], szX, szY;


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);
	
	szX = unique(X + 1, X + 1 + n) - X - 1;
	szY = unique(Y + 1, Y + 1 + n) - Y - 1;

	forn (i, 1, n) {
		d[i].x = lower_bound(X + 1, X + 1 + szX, d[i].x) - X;
		d[i].y = lower_bound(Y + 1, Y + 1 + szY, 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 + szX, e[i].a) - X;
		e[i].b = lower_bound(Y + 1, Y + 1 + szY, 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 1144 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 1148 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 14 ms 4216 KB Output is correct
11 Correct 11 ms 2424 KB Output is correct
12 Correct 8 ms 1272 KB Output is correct
13 Correct 24 ms 8184 KB Output is correct
14 Correct 23 ms 8188 KB Output is correct
15 Correct 23 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 1144 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1636 ms 349892 KB Output is correct
2 Correct 1611 ms 350712 KB Output is correct
3 Correct 1634 ms 350764 KB Output is correct
4 Correct 485 ms 74232 KB Output is correct
5 Correct 294 ms 35832 KB Output is correct
6 Correct 89 ms 6008 KB Output is correct
7 Correct 1545 ms 350876 KB Output is correct
8 Correct 1490 ms 350328 KB Output is correct
9 Correct 1237 ms 349944 KB Output is correct
10 Correct 142 ms 17528 KB Output is correct
11 Correct 396 ms 59384 KB Output is correct
12 Correct 54 ms 5496 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 1636 ms 349892 KB Output is correct
2 Correct 1611 ms 350712 KB Output is correct
3 Correct 1634 ms 350764 KB Output is correct
4 Correct 485 ms 74232 KB Output is correct
5 Correct 294 ms 35832 KB Output is correct
6 Correct 89 ms 6008 KB Output is correct
7 Correct 1545 ms 350876 KB Output is correct
8 Correct 1490 ms 350328 KB Output is correct
9 Correct 1237 ms 349944 KB Output is correct
10 Correct 142 ms 17528 KB Output is correct
11 Correct 396 ms 59384 KB Output is correct
12 Correct 54 ms 5496 KB Output is correct
13 Correct 1350 ms 350328 KB Output is correct
14 Correct 1604 ms 350584 KB Output is correct
15 Correct 1619 ms 350456 KB Output is correct
16 Correct 387 ms 74104 KB Output is correct
17 Correct 244 ms 35576 KB Output is correct
18 Correct 89 ms 5752 KB Output is correct
19 Correct 1335 ms 350456 KB Output is correct
20 Correct 1457 ms 350676 KB Output is correct
21 Correct 1146 ms 350328 KB Output is correct
22 Correct 151 ms 17456 KB Output is correct
23 Correct 375 ms 58744 KB Output is correct
24 Correct 54 ms 5240 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 1144 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 1148 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 14 ms 4216 KB Output is correct
11 Correct 11 ms 2424 KB Output is correct
12 Correct 8 ms 1272 KB Output is correct
13 Correct 24 ms 8184 KB Output is correct
14 Correct 23 ms 8188 KB Output is correct
15 Correct 23 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 1144 KB Output is correct
19 Correct 1636 ms 349892 KB Output is correct
20 Correct 1611 ms 350712 KB Output is correct
21 Correct 1634 ms 350764 KB Output is correct
22 Correct 485 ms 74232 KB Output is correct
23 Correct 294 ms 35832 KB Output is correct
24 Correct 89 ms 6008 KB Output is correct
25 Correct 1545 ms 350876 KB Output is correct
26 Correct 1490 ms 350328 KB Output is correct
27 Correct 1237 ms 349944 KB Output is correct
28 Correct 142 ms 17528 KB Output is correct
29 Correct 396 ms 59384 KB Output is correct
30 Correct 54 ms 5496 KB Output is correct
31 Correct 1350 ms 350328 KB Output is correct
32 Correct 1604 ms 350584 KB Output is correct
33 Correct 1619 ms 350456 KB Output is correct
34 Correct 387 ms 74104 KB Output is correct
35 Correct 244 ms 35576 KB Output is correct
36 Correct 89 ms 5752 KB Output is correct
37 Correct 1335 ms 350456 KB Output is correct
38 Correct 1457 ms 350676 KB Output is correct
39 Correct 1146 ms 350328 KB Output is correct
40 Correct 151 ms 17456 KB Output is correct
41 Correct 375 ms 58744 KB Output is correct
42 Correct 54 ms 5240 KB Output is correct
43 Correct 1414 ms 403400 KB Output is correct
44 Correct 1390 ms 403384 KB Output is correct
45 Correct 1610 ms 403448 KB Output is correct
46 Correct 457 ms 104568 KB Output is correct
47 Correct 269 ms 43260 KB Output is correct
48 Correct 80 ms 5240 KB Output is correct
49 Correct 1483 ms 403448 KB Output is correct
50 Correct 1192 ms 403536 KB Output is correct
51 Correct 1097 ms 403192 KB Output is correct
52 Correct 174 ms 23800 KB Output is correct
53 Correct 439 ms 89720 KB Output is correct