oj.uz

Submission #927823

# Submission time Handle Problem Language Result Execution time Memory
927823 2024-02-15T11:09:08 Z hqminhuwu Examination (JOI19_examination) C++14
100 / 100
 1536 ms 28312 KB 
#include <bits/stdc++.h>
#define forr(_a,_b,_c) for(_a = (_b); _a <= (_c); ++_a)
#define ford(_a,_b,_c) for(_a = (_b) + 1; _a --> (_c);)
#define forf(_a,_b,_c) for(_a = (_b); _a < (_c); ++_a)
#define st first
#define nd second
#define ll long long
#define ull unsigned long long
#define pii pair <int,int>
#define pll pair <ll,ll>
#define piii pair <int,pii>
#define vi vector <int>
#define pb push_back
#define mp make_pair
#define all(x) begin(x),end(x)
#define file "test"


using namespace std;
const int N = 5e5 + 5;
const ll oo = 1e9;
const ll mod = 1e9 + 7;
const int uwu = 317;

pair <pii, pii> w[N];
int bit[uwu + 5][uwu + 5], n, q, i, j, k, ans[N], flag[N];
pii a[N];
vector <pii> f;
vi v[N];

void update (int id, int x){
	for (; x > 0; x -= x & -x)
		bit[id][x]++;
}

int get (int id, int x){
	int res = 0;
	for (; x <= uwu + 1; x += x & -x)
		res += bit[id][x];
	return res;
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	#ifdef hqm
	   freopen(file".inp", "r", stdin); freopen(file".out", "w", stdout);
	#endif

	cin >> n >> q;
	
	forr (i, 1, n)
		cin >> a[i].st >> a[i].nd;
	
	sort(a + 1, a + 1+ n);
	
	forr (i, 1, n)
		f.pb({a[i].st + a[i].nd, i});
	
	forr (i, 1, n)
		v[i / uwu].pb(a[i].nd);

	forr (i, 0, n / uwu){
		sort(all(v[i])), v[i].erase(unique(all(v[i])), v[i].end());
	}

	forr (i, 1, q)
		cin >> w[i].nd.st >> w[i].nd.nd >> w[i].st.st, w[i].st.nd = i;
	
	sort(w + 1, w + 1 + n, greater<pair<pii, pii>>());
	sort(all(f));

	int it = f.size() - 1;

	forr (i, 1, q){
		int z = w[i].st.st, x = w[i].nd.st, y = w[i].nd.nd, pos = w[i].st.nd;
		while (it >= 0 && f[it].st >= z){
			int id = f[it].nd / uwu;
			flag[f[it].nd] = 1;
			int tmp = lower_bound(all(v[id]), a[f[it].nd].nd) - v[id].begin() + 1;
			//cout << f[it].st << " " << a[f[it].nd].st << " " << a[f[it].nd].nd << " " << id << " " << tmp << "\n";
			update(id, tmp);
			it--;
		}

		int j = n / uwu;
		while (j >= 0 && a[uwu * j].st >= x){
			int e = lower_bound(all(v[j]), y) - v[j].begin() + 1;
		//	cout << e << "\n";
			ans[pos] += get(j, e);
			j--;
		}

		if (j >= 0)
		ford (k, uwu * (j + 1) - 1, j * uwu){
			ans[pos] += (y <= a[k].nd && x <= a[k].st) * flag[k];
		}
	//	cout << y << "\n";
	}

	forr (i, 1, q)
		cout << ans[i] << "\n";
	return 0;
}
/*



*/

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14940 KB Output is correct
2 Correct 4 ms 14988 KB Output is correct
3 Correct 4 ms 17028 KB Output is correct
4 Correct 4 ms 14940 KB Output is correct
5 Correct 4 ms 15084 KB Output is correct
6 Correct 4 ms 14940 KB Output is correct
7 Correct 12 ms 15260 KB Output is correct
8 Correct 9 ms 15196 KB Output is correct
9 Correct 9 ms 15196 KB Output is correct
10 Correct 11 ms 15184 KB Output is correct
11 Correct 7 ms 15196 KB Output is correct
12 Correct 6 ms 16988 KB Output is correct
13 Correct 12 ms 17244 KB Output is correct
14 Correct 9 ms 17240 KB Output is correct
15 Correct 11 ms 17244 KB Output is correct
16 Correct 7 ms 16988 KB Output is correct
17 Correct 8 ms 15196 KB Output is correct
18 Correct 6 ms 15196 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 908 ms 25844 KB Output is correct
2 Correct 992 ms 25964 KB Output is correct
3 Correct 938 ms 25916 KB Output is correct
4 Correct 484 ms 25172 KB Output is correct
5 Correct 591 ms 25140 KB Output is correct
6 Correct 306 ms 24556 KB Output is correct
7 Correct 1536 ms 25916 KB Output is correct
8 Correct 625 ms 25828 KB Output is correct
9 Correct 1083 ms 25860 KB Output is correct
10 Correct 370 ms 24864 KB Output is correct
11 Correct 247 ms 25084 KB Output is correct
12 Correct 144 ms 24016 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 908 ms 25844 KB Output is correct
2 Correct 992 ms 25964 KB Output is correct
3 Correct 938 ms 25916 KB Output is correct
4 Correct 484 ms 25172 KB Output is correct
5 Correct 591 ms 25140 KB Output is correct
6 Correct 306 ms 24556 KB Output is correct
7 Correct 1536 ms 25916 KB Output is correct
8 Correct 625 ms 25828 KB Output is correct
9 Correct 1083 ms 25860 KB Output is correct
10 Correct 370 ms 24864 KB Output is correct
11 Correct 247 ms 25084 KB Output is correct
12 Correct 144 ms 24016 KB Output is correct
13 Correct 902 ms 24756 KB Output is correct
14 Correct 905 ms 26348 KB Output is correct
15 Correct 879 ms 26176 KB Output is correct
16 Correct 370 ms 25608 KB Output is correct
17 Correct 452 ms 25612 KB Output is correct
18 Correct 350 ms 24504 KB Output is correct
19 Correct 898 ms 24576 KB Output is correct
20 Correct 935 ms 26380 KB Output is correct
21 Correct 1161 ms 24732 KB Output is correct
22 Correct 360 ms 25096 KB Output is correct
23 Correct 258 ms 25036 KB Output is correct
24 Correct 146 ms 24120 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 14940 KB Output is correct
2 Correct 4 ms 14988 KB Output is correct
3 Correct 4 ms 17028 KB Output is correct
4 Correct 4 ms 14940 KB Output is correct
5 Correct 4 ms 15084 KB Output is correct
6 Correct 4 ms 14940 KB Output is correct
7 Correct 12 ms 15260 KB Output is correct
8 Correct 9 ms 15196 KB Output is correct
9 Correct 9 ms 15196 KB Output is correct
10 Correct 11 ms 15184 KB Output is correct
11 Correct 7 ms 15196 KB Output is correct
12 Correct 6 ms 16988 KB Output is correct
13 Correct 12 ms 17244 KB Output is correct
14 Correct 9 ms 17240 KB Output is correct
15 Correct 11 ms 17244 KB Output is correct
16 Correct 7 ms 16988 KB Output is correct
17 Correct 8 ms 15196 KB Output is correct
18 Correct 6 ms 15196 KB Output is correct
19 Correct 908 ms 25844 KB Output is correct
20 Correct 992 ms 25964 KB Output is correct
21 Correct 938 ms 25916 KB Output is correct
22 Correct 484 ms 25172 KB Output is correct
23 Correct 591 ms 25140 KB Output is correct
24 Correct 306 ms 24556 KB Output is correct
25 Correct 1536 ms 25916 KB Output is correct
26 Correct 625 ms 25828 KB Output is correct
27 Correct 1083 ms 25860 KB Output is correct
28 Correct 370 ms 24864 KB Output is correct
29 Correct 247 ms 25084 KB Output is correct
30 Correct 144 ms 24016 KB Output is correct
31 Correct 902 ms 24756 KB Output is correct
32 Correct 905 ms 26348 KB Output is correct
33 Correct 879 ms 26176 KB Output is correct
34 Correct 370 ms 25608 KB Output is correct
35 Correct 452 ms 25612 KB Output is correct
36 Correct 350 ms 24504 KB Output is correct
37 Correct 898 ms 24576 KB Output is correct
38 Correct 935 ms 26380 KB Output is correct
39 Correct 1161 ms 24732 KB Output is correct
40 Correct 360 ms 25096 KB Output is correct
41 Correct 258 ms 25036 KB Output is correct
42 Correct 146 ms 24120 KB Output is correct
43 Correct 895 ms 26708 KB Output is correct
44 Correct 874 ms 26608 KB Output is correct
45 Correct 889 ms 28312 KB Output is correct
46 Correct 382 ms 26572 KB Output is correct
47 Correct 413 ms 26824 KB Output is correct
48 Correct 287 ms 22724 KB Output is correct
49 Correct 1514 ms 28204 KB Output is correct
50 Correct 668 ms 26600 KB Output is correct
51 Correct 1118 ms 28112 KB Output is correct
52 Correct 375 ms 26508 KB Output is correct
53 Correct 388 ms 25664 KB Output is correct