oj.uz

Submission #839421

# Submission time Handle Problem Language Result Execution time Memory
839421 2023-08-30T02:41:39 Z vjudge1 Examination (JOI19_examination) C++17
100 / 100
 2775 ms 89696 KB 
#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:112:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  112 |  for (int i = 0; i < sorted_arr.size(); i++)
      |                  ~~^~~~~~~~~~~~~~~~~~~
examination.cpp:120:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |  for (int ii = 0; ii < id2.size(); ii++){
      |                   ~~~^~~~~~~~~~~~
examination.cpp:122:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  122 |   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 3 ms 7380 KB Output is correct
3 Correct 3 ms 7380 KB Output is correct
4 Correct 3 ms 7380 KB Output is correct
5 Correct 3 ms 7380 KB Output is correct
6 Correct 3 ms 7380 KB Output is correct
7 Correct 22 ms 9676 KB Output is correct
8 Correct 21 ms 9684 KB Output is correct
9 Correct 22 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 7632 KB Output is correct
13 Correct 19 ms 9684 KB Output is correct
14 Correct 18 ms 9684 KB Output is correct
15 Correct 19 ms 9684 KB Output is correct
16 Correct 19 ms 9044 KB Output is correct
17 Correct 11 ms 8020 KB Output is correct
18 Correct 4 ms 7508 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 779 ms 67624 KB Output is correct
2 Correct 757 ms 67388 KB Output is correct
3 Correct 808 ms 67548 KB Output is correct
4 Correct 353 ms 28600 KB Output is correct
5 Correct 734 ms 45112 KB Output is correct
6 Correct 176 ms 11592 KB Output is correct
7 Correct 1052 ms 67276 KB Output is correct
8 Correct 786 ms 67168 KB Output is correct
9 Correct 1081 ms 67612 KB Output is correct
10 Correct 643 ms 41972 KB Output is correct
11 Correct 280 ms 20188 KB Output is correct
12 Correct 47 ms 10824 KB Output is correct

Subtask #3
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 779 ms 67624 KB Output is correct
2 Correct 757 ms 67388 KB Output is correct
3 Correct 808 ms 67548 KB Output is correct
4 Correct 353 ms 28600 KB Output is correct
5 Correct 734 ms 45112 KB Output is correct
6 Correct 176 ms 11592 KB Output is correct
7 Correct 1052 ms 67276 KB Output is correct
8 Correct 786 ms 67168 KB Output is correct
9 Correct 1081 ms 67612 KB Output is correct
10 Correct 643 ms 41972 KB Output is correct
11 Correct 280 ms 20188 KB Output is correct
12 Correct 47 ms 10824 KB Output is correct
13 Correct 1368 ms 67256 KB Output is correct
14 Correct 1022 ms 67528 KB Output is correct
15 Correct 773 ms 67596 KB Output is correct
16 Correct 403 ms 28640 KB Output is correct
17 Correct 757 ms 45144 KB Output is correct
18 Correct 183 ms 11592 KB Output is correct
19 Correct 1339 ms 67296 KB Output is correct
20 Correct 1262 ms 67328 KB Output is correct
21 Correct 1758 ms 67284 KB Output is correct
22 Correct 624 ms 41892 KB Output is correct
23 Correct 278 ms 20108 KB Output is correct
24 Correct 48 ms 10900 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 3 ms 7380 KB Output is correct
3 Correct 3 ms 7380 KB Output is correct
4 Correct 3 ms 7380 KB Output is correct
5 Correct 3 ms 7380 KB Output is correct
6 Correct 3 ms 7380 KB Output is correct
7 Correct 22 ms 9676 KB Output is correct
8 Correct 21 ms 9684 KB Output is correct
9 Correct 22 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 7632 KB Output is correct
13 Correct 19 ms 9684 KB Output is correct
14 Correct 18 ms 9684 KB Output is correct
15 Correct 19 ms 9684 KB Output is correct
16 Correct 19 ms 9044 KB Output is correct
17 Correct 11 ms 8020 KB Output is correct
18 Correct 4 ms 7508 KB Output is correct
19 Correct 779 ms 67624 KB Output is correct
20 Correct 757 ms 67388 KB Output is correct
21 Correct 808 ms 67548 KB Output is correct
22 Correct 353 ms 28600 KB Output is correct
23 Correct 734 ms 45112 KB Output is correct
24 Correct 176 ms 11592 KB Output is correct
25 Correct 1052 ms 67276 KB Output is correct
26 Correct 786 ms 67168 KB Output is correct
27 Correct 1081 ms 67612 KB Output is correct
28 Correct 643 ms 41972 KB Output is correct
29 Correct 280 ms 20188 KB Output is correct
30 Correct 47 ms 10824 KB Output is correct
31 Correct 1368 ms 67256 KB Output is correct
32 Correct 1022 ms 67528 KB Output is correct
33 Correct 773 ms 67596 KB Output is correct
34 Correct 403 ms 28640 KB Output is correct
35 Correct 757 ms 45144 KB Output is correct
36 Correct 183 ms 11592 KB Output is correct
37 Correct 1339 ms 67296 KB Output is correct
38 Correct 1262 ms 67328 KB Output is correct
39 Correct 1758 ms 67284 KB Output is correct
40 Correct 624 ms 41892 KB Output is correct
41 Correct 278 ms 20108 KB Output is correct
42 Correct 48 ms 10900 KB Output is correct
43 Correct 1613 ms 89484 KB Output is correct
44 Correct 1624 ms 89680 KB Output is correct
45 Correct 1103 ms 89604 KB Output is correct
46 Correct 468 ms 41008 KB Output is correct
47 Correct 790 ms 70756 KB Output is correct
48 Correct 105 ms 11240 KB Output is correct
49 Correct 1877 ms 89696 KB Output is correct
50 Correct 1950 ms 89588 KB Output is correct
51 Correct 2775 ms 89464 KB Output is correct
52 Correct 758 ms 59868 KB Output is correct
53 Correct 300 ms 24820 KB Output is correct