oj.uz

Submission #804412

# Submission time Handle Problem Language Result Execution time Memory
804412 2023-08-03T08:34:34 Z 박상훈(#10101) Vera and Modern Art (CCO17_art) C++17
25 / 25
 1128 ms 245096 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

int T[40004000], L[40004000], R[40004000];
int sz;

inline int alloc1(){return ++sz;}

struct Trie{
	int root;

	void push(int i, int dep, int len, ll x, int val){
		if (dep==len) {T[i] += val; return;}

		if (x&(1LL<<dep)){
			if (R[i]==0) R[i] = alloc1();
			push(R[i], dep+1, len, x, val);
		}

		else{
			if (L[i]==0) L[i] = alloc1();
			push(L[i], dep+1, len, x, val);
		}
	}

	int query(int i, int dep, int len, ll x){
		if (dep==len) return T[i];
		if (!i) return 0;

		if (x&(1LL<<dep)) return T[i] + query(R[i], dep+1, len, x);
		return T[i] + query(L[i], dep+1, len, x);
	}

	void push(int len, ll x, int val){
		if (root==0) root = alloc1();
		push(root, 0, len, x, val);
	}

	int query(int len, ll x){return query(root, 0, len, x);}
};

struct Trie2D{
	Trie T[20002000];
	int L[20002000], R[20002000];
	int sz;

	inline int alloc2(){return ++sz;}

	void push(int i, int dep, int lenx, ll x, int leny, ll y, int val){
		if (dep==lenx) {T[i].push(leny, y, val); return;}

		if (x&(1LL<<dep)){
			if (R[i]==0) R[i] = alloc2();
			push(R[i], dep+1, lenx, x, leny, y, val);
		}

		else{
			if (L[i]==0) L[i] = alloc2();
			push(L[i], dep+1, lenx, x, leny, y, val);
		}
	}

	int query(int i, int dep, int lenx, ll x, int leny, ll y){
		if (dep==lenx) return T[i].query(leny, y);
		if (i==0) return 0;

		if (x&(1LL<<dep)){
			return T[i].query(leny, y) + query(R[i], dep+1, lenx, x, leny, y);
		}

		return T[i].query(leny, y) + query(L[i], dep+1, lenx, x, leny, y);
	}
}trie;

struct Node{
	ll x, y;
	int sum;

	Node(){}
	Node(ll _x, ll _y, int _sum): x(_x), y(_y), sum(_sum) {}

	bool operator < (const Node &N) const{
		return tie(x, y) < tie(N.x, N.y);
	}
};

int n, q;

int a[200200];
ll X[200200], Y[200200];

void init(){
	trie.alloc2();

	for (int i=1;i<=n;i++){
		int z = 0;
		for (;(1LL<<z)<=X[i];z++);
		--z;

		int lenx = z;

		z = 0;
		for (;(1LL<<z)<=Y[i];z++);
		--z;

		int leny = z;

		ll nx = X[i] & ((1LL<<lenx)-1);
		ll ny = Y[i] & ((1LL<<leny)-1);
		trie.push(1, 0, lenx, nx, leny, ny, a[i]);
	}
}

int main(){
	scanf("%d %d", &n, &q);
	for (int i=1;i<=n;i++) scanf("%lld %lld %d", X+i, Y+i, a+i);

	init();

	while(q--){
		ll x, y;
		scanf("%lld %lld", &x, &y);

		int z = 0;
		for (;(1LL<<z)<=x;z++);
		--z;

		int lenx = z;

		z = 0;
		for (;(1LL<<z)<=y;z++);
		--z;

		int leny = z;

		ll nx = x & ((1LL<<lenx)-1);
		ll ny = y & ((1LL<<leny)-1);

		int ans = trie.query(1, 0, lenx, nx, leny, ny);
		printf("%d\n", ans);
	}
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:117:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  117 |  scanf("%d %d", &n, &q);
      |  ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:118:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |  for (int i=1;i<=n;i++) scanf("%lld %lld %d", X+i, Y+i, a+i);
      |                         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Main.cpp:124:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  124 |   scanf("%lld %lld", &x, &y);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 6 ms 2924 KB Output is correct
3 Correct 6 ms 2992 KB Output is correct
4 Correct 4 ms 1492 KB Output is correct
5 Correct 4 ms 1480 KB Output is correct
6 Correct 3 ms 1612 KB Output is correct
7 Correct 4 ms 1620 KB Output is correct
8 Correct 3 ms 1620 KB Output is correct
9 Correct 4 ms 1620 KB Output is correct
10 Correct 4 ms 1620 KB Output is correct
11 Correct 3 ms 1620 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 537 ms 105272 KB Output is correct
2 Correct 605 ms 105008 KB Output is correct
3 Correct 367 ms 36760 KB Output is correct
4 Correct 348 ms 36884 KB Output is correct
5 Correct 277 ms 43348 KB Output is correct
6 Correct 281 ms 43360 KB Output is correct
7 Correct 262 ms 43328 KB Output is correct
8 Correct 272 ms 43400 KB Output is correct
9 Correct 272 ms 43388 KB Output is correct
10 Correct 294 ms 43428 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 242 ms 53284 KB Output is correct
3 Correct 239 ms 53304 KB Output is correct
4 Correct 304 ms 22848 KB Output is correct
5 Correct 299 ms 22988 KB Output is correct
6 Correct 194 ms 23336 KB Output is correct
7 Correct 195 ms 23196 KB Output is correct
8 Correct 204 ms 23264 KB Output is correct
9 Correct 232 ms 23312 KB Output is correct
10 Correct 196 ms 23280 KB Output is correct
11 Correct 208 ms 23216 KB Output is correct

Subtask #4
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 6 ms 2924 KB Output is correct
3 Correct 6 ms 2992 KB Output is correct
4 Correct 4 ms 1492 KB Output is correct
5 Correct 4 ms 1480 KB Output is correct
6 Correct 3 ms 1612 KB Output is correct
7 Correct 4 ms 1620 KB Output is correct
8 Correct 3 ms 1620 KB Output is correct
9 Correct 4 ms 1620 KB Output is correct
10 Correct 4 ms 1620 KB Output is correct
11 Correct 3 ms 1620 KB Output is correct
12 Correct 537 ms 105272 KB Output is correct
13 Correct 605 ms 105008 KB Output is correct
14 Correct 367 ms 36760 KB Output is correct
15 Correct 348 ms 36884 KB Output is correct
16 Correct 277 ms 43348 KB Output is correct
17 Correct 281 ms 43360 KB Output is correct
18 Correct 262 ms 43328 KB Output is correct
19 Correct 272 ms 43400 KB Output is correct
20 Correct 272 ms 43388 KB Output is correct
21 Correct 294 ms 43428 KB Output is correct
22 Correct 1 ms 340 KB Output is correct
23 Correct 242 ms 53284 KB Output is correct
24 Correct 239 ms 53304 KB Output is correct
25 Correct 304 ms 22848 KB Output is correct
26 Correct 299 ms 22988 KB Output is correct
27 Correct 194 ms 23336 KB Output is correct
28 Correct 195 ms 23196 KB Output is correct
29 Correct 204 ms 23264 KB Output is correct
30 Correct 232 ms 23312 KB Output is correct
31 Correct 196 ms 23280 KB Output is correct
32 Correct 208 ms 23216 KB Output is correct
33 Correct 808 ms 245020 KB Output is correct
34 Correct 821 ms 245096 KB Output is correct
35 Correct 1038 ms 105236 KB Output is correct
36 Correct 1128 ms 105284 KB Output is correct
37 Correct 786 ms 111664 KB Output is correct
38 Correct 876 ms 111916 KB Output is correct
39 Correct 904 ms 111836 KB Output is correct
40 Correct 765 ms 111764 KB Output is correct
41 Correct 715 ms 111804 KB Output is correct
42 Correct 723 ms 111544 KB Output is correct