oj.uz

Submission #839422

# Submission time Handle Problem Language Result Execution time Memory
839422 2023-08-30T02:45:50 Z daoquanglinh2007 Examination (JOI19_examination) C++17
100 / 100
 2954 ms 89720 KB 
#pragma GCC optimize("Ofast")
#pragma GCC target("sse4")

#include <bits/stdc++.h>
using namespace std;

#define getbit(x, i) ((x&(1<<(i))) != 0)

const int NM = 3e5, SZ = 550, LOG = 18;

struct node{
	mutable int cnt, nxt[2];
	node(int a, int b, int c){
		cnt = a, nxt[0] = b, nxt[1] = c;
	}
};

struct trie{
	vector <node> T;
	void add_node(){
		T.push_back(node(0, -1, -1));
	}
	void init(){
		T.clear();
		add_node();
	}
	void add_int(int x){
		int cur = 0;
		for (int i = LOG; i >= 0; i--){
			T[cur].cnt++;
			int k = getbit(x, i);
			if (T[cur].nxt[k] == -1){
				add_node();
				T[cur].nxt[k] = T.size()-1;
			}
			cur = T[cur].nxt[k];
		}
		T[cur].cnt++;
	}
	int get(int x){
		int cur = 0, res = 0;
		for (int i = LOG; i >= 0; i--){
			int k = getbit(x, i);
			if (k == 0){
				if (T[cur].nxt[1] != -1) res += T[T[cur].nxt[1]].cnt;
			}
			if (T[cur].nxt[k] == -1) return res;
			cur = T[cur].nxt[k];
		}
		res += T[cur].cnt;
		return res;
	}
};

int N, Q;
int S[NM+5], T[NM+5], sum[NM+5], X[NM+5], Y[NM+5], Z[NM+5];
map <int, bool> mark;
vector <int> sorted_arr, id1, id2;
int ans[NM+5];
trie T1[NM+5], T2[SZ+5];

int get(int x){
	if (sorted_arr.back() < x) return -1;
	return lower_bound(sorted_arr.begin(), sorted_arr.end(), x)-sorted_arr.begin();
}

bool cmp1(int x, int y){
	return S[x] > S[y];
}

bool cmp2(int x, int y){
	return X[x] > X[y];
}

int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> N >> Q;
	for (int i = 1; i <= N; i++){
		cin >> S[i] >> T[i];
		if (!mark[S[i]]){
			sorted_arr.push_back(S[i]);
			mark[S[i]] = 1;
		}
		if (!mark[T[i]]){
			sorted_arr.push_back(T[i]);
			mark[T[i]] = 1;
		}
		sum[i] = S[i]+T[i];
		if (!mark[sum[i]]){
			sorted_arr.push_back(sum[i]);
			mark[sum[i]] = 1;
		}
		id1.push_back(i);
	}
	sort(sorted_arr.begin(), sorted_arr.end());
	for (int i = 1; i <= N; i++){
		S[i] = lower_bound(sorted_arr.begin(), sorted_arr.end(), S[i])-sorted_arr.begin();
		T[i] = lower_bound(sorted_arr.begin(), sorted_arr.end(), T[i])-sorted_arr.begin();
		sum[i] = lower_bound(sorted_arr.begin(), sorted_arr.end(), sum[i])-sorted_arr.begin();
	}
	for (int i = 1; i <= Q; i++){
		cin >> X[i] >> Y[i] >> Z[i];
		X[i] = get(X[i]);
		Y[i] = get(Y[i]);
		Z[i] = get(Z[i]);
		if (X[i] == -1 || Y[i] == -1 || Z[i] == -1){
			ans[i] = 0;
		}
		else{
			id2.push_back(i);
		}
	}
	for (int i = 0; i < sorted_arr.size(); i++)
		T1[i].init();
	for (int i = 0; i < SZ; i++)
		T2[i].init();
	sort(id1.begin(), id1.end(), cmp1);
	sort(id2.begin(), id2.end(), cmp2);
	
	int jj = 0;
	for (int ii = 0; ii < id2.size(); ii++){
		int i = id2[ii];
		while (jj < id1.size()){
			int j = id1[jj];
			if (S[j] < X[i]) break;
			T1[T[j]].add_int(sum[j]);
			T2[T[j]/SZ].add_int(sum[j]);
			jj++;
		}
		ans[i] = 0;
		int L = (Y[i]+SZ-1)/SZ;
		for (int k = L; k < SZ; k++)
			ans[i] += T2[k].get(Z[i]);
		for (int k = Y[i]; k < min((int)sorted_arr.size(), L*SZ); k++)
			ans[i] += T1[k].get(Z[i]);
	}
	for (int i = 1; i <= Q; i++) cout << ans[i] << '\n';
	return 0;
}

Compilation message

examination.cpp: In function 'int main()':
examination.cpp:115:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  115 |  for (int i = 0; i < sorted_arr.size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~~~~
examination.cpp:123:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  123 |  for (int ii = 0; ii < id2.size(); ii++){
      |                   ~~~^~~~~~~~~~~~
examination.cpp:125:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  125 |   while (jj < id1.size()){
      |          ~~~^~~~~~~~~~~~

Subtask #1
2.0 / 2.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7448 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 22 ms 9708 KB Output is correct
8 Correct 22 ms 9684 KB Output is correct
9 Correct 23 ms 9684 KB Output is correct
10 Correct 16 ms 8532 KB Output is correct
11 Correct 20 ms 9300 KB Output is correct
12 Correct 9 ms 7508 KB Output is correct
13 Correct 20 ms 9684 KB Output is correct
14 Correct 21 ms 9684 KB Output is correct
15 Correct 19 ms 9684 KB Output is correct
16 Correct 20 ms 9044 KB Output is correct
17 Correct 12 ms 8020 KB Output is correct
18 Correct 5 ms 7508 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 795 ms 67372 KB Output is correct
2 Correct 849 ms 67488 KB Output is correct
3 Correct 812 ms 67516 KB Output is correct
4 Correct 371 ms 28572 KB Output is correct
5 Correct 720 ms 45180 KB Output is correct
6 Correct 182 ms 11596 KB Output is correct
7 Correct 1018 ms 67268 KB Output is correct
8 Correct 769 ms 67156 KB Output is correct
9 Correct 1100 ms 67428 KB Output is correct
10 Correct 655 ms 41864 KB Output is correct
11 Correct 304 ms 20208 KB Output is correct
12 Correct 56 ms 10816 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 795 ms 67372 KB Output is correct
2 Correct 849 ms 67488 KB Output is correct
3 Correct 812 ms 67516 KB Output is correct
4 Correct 371 ms 28572 KB Output is correct
5 Correct 720 ms 45180 KB Output is correct
6 Correct 182 ms 11596 KB Output is correct
7 Correct 1018 ms 67268 KB Output is correct
8 Correct 769 ms 67156 KB Output is correct
9 Correct 1100 ms 67428 KB Output is correct
10 Correct 655 ms 41864 KB Output is correct
11 Correct 304 ms 20208 KB Output is correct
12 Correct 56 ms 10816 KB Output is correct
13 Correct 1321 ms 67484 KB Output is correct
14 Correct 1006 ms 67456 KB Output is correct
15 Correct 778 ms 67628 KB Output is correct
16 Correct 416 ms 28704 KB Output is correct
17 Correct 801 ms 45124 KB Output is correct
18 Correct 184 ms 11600 KB Output is correct
19 Correct 1364 ms 67348 KB Output is correct
20 Correct 1293 ms 67268 KB Output is correct
21 Correct 1794 ms 67252 KB Output is correct
22 Correct 636 ms 41932 KB Output is correct
23 Correct 287 ms 20148 KB Output is correct
24 Correct 55 ms 10816 KB Output is correct

Subtask #4
57.0 / 57.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7380 KB Output is correct
2 Correct 4 ms 7380 KB Output is correct
3 Correct 4 ms 7380 KB Output is correct
4 Correct 4 ms 7448 KB Output is correct
5 Correct 4 ms 7380 KB Output is correct
6 Correct 4 ms 7380 KB Output is correct
7 Correct 22 ms 9708 KB Output is correct
8 Correct 22 ms 9684 KB Output is correct
9 Correct 23 ms 9684 KB Output is correct
10 Correct 16 ms 8532 KB Output is correct
11 Correct 20 ms 9300 KB Output is correct
12 Correct 9 ms 7508 KB Output is correct
13 Correct 20 ms 9684 KB Output is correct
14 Correct 21 ms 9684 KB Output is correct
15 Correct 19 ms 9684 KB Output is correct
16 Correct 20 ms 9044 KB Output is correct
17 Correct 12 ms 8020 KB Output is correct
18 Correct 5 ms 7508 KB Output is correct
19 Correct 795 ms 67372 KB Output is correct
20 Correct 849 ms 67488 KB Output is correct
21 Correct 812 ms 67516 KB Output is correct
22 Correct 371 ms 28572 KB Output is correct
23 Correct 720 ms 45180 KB Output is correct
24 Correct 182 ms 11596 KB Output is correct
25 Correct 1018 ms 67268 KB Output is correct
26 Correct 769 ms 67156 KB Output is correct
27 Correct 1100 ms 67428 KB Output is correct
28 Correct 655 ms 41864 KB Output is correct
29 Correct 304 ms 20208 KB Output is correct
30 Correct 56 ms 10816 KB Output is correct
31 Correct 1321 ms 67484 KB Output is correct
32 Correct 1006 ms 67456 KB Output is correct
33 Correct 778 ms 67628 KB Output is correct
34 Correct 416 ms 28704 KB Output is correct
35 Correct 801 ms 45124 KB Output is correct
36 Correct 184 ms 11600 KB Output is correct
37 Correct 1364 ms 67348 KB Output is correct
38 Correct 1293 ms 67268 KB Output is correct
39 Correct 1794 ms 67252 KB Output is correct
40 Correct 636 ms 41932 KB Output is correct
41 Correct 287 ms 20148 KB Output is correct
42 Correct 55 ms 10816 KB Output is correct
43 Correct 1684 ms 89556 KB Output is correct
44 Correct 1688 ms 89548 KB Output is correct
45 Correct 1279 ms 89492 KB Output is correct
46 Correct 473 ms 41008 KB Output is correct
47 Correct 872 ms 70804 KB Output is correct
48 Correct 113 ms 11212 KB Output is correct
49 Correct 1927 ms 89588 KB Output is correct
50 Correct 2090 ms 89720 KB Output is correct
51 Correct 2954 ms 89468 KB Output is correct
52 Correct 800 ms 59796 KB Output is correct
53 Correct 312 ms 24888 KB Output is correct