oj.uz

Submission #804164

# Submission time Handle Problem Language Result Execution time Memory
804164 2023-08-03T07:26:27 Z 박상훈(#10101) Vera and Modern Art (CCO17_art) C++17
5 / 25
 925 ms 1048576 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

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];

vector<Node> buf[64][64], FUCK[64][64];

int lenx[200200], leny[200200], rans[200200];


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

		lenx[i] = z;

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

		leny[i] = z;

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

	for (int i=0;i<64;i++){
		for (int j=0;j<64;j++){
			sort(buf[i][j].begin(), buf[i][j].end());
			for (int k=1;k<(int)buf[i][j].size();k++) if (buf[i][j][k].x == buf[i][j][k-1].x && buf[i][j][k].y == buf[i][j][k-1].y){
				buf[i][j][k].sum += buf[i][j][k-1].sum;
			}
		}
	}
}

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();

	for (int z=1;z<=q;z++){
		ll x, y;
		scanf("%lld %lld", &x, &y);

		// int ans = 0;

		for (int i=0;(1LL<<i)<=x;i++){
			ll nx = x & ((1LL<<i)-1);
			for (int j=0;(1LL<<j)<=y;j++){
				ll ny = y & ((1LL<<j)-1);

				FUCK[i][j].emplace_back(nx, ny, z);
				// auto iter = upper_bound(buf[i][j].begin(), buf[i][j].end(), Node(nx, ny, 0));
				
				// if (iter==buf[i][j].begin()) continue;
				// --iter;
				// if (iter->x == nx && iter->y == ny) ans += iter->sum;
			}
		}

		


		// printf("%d\n", ans);
	}

	for (int i=0;i<64;i++){
		for (int j=0;j<64;j++) if (!buf[i][j].empty()){
			sort(FUCK[i][j].begin(), FUCK[i][j].end());
			for (int k=0;k<(int)buf[i][j].size();k++){
				if (k<(int)buf[i][j].size()-1 && buf[i][j][k].x == buf[i][j][k+1].x && buf[i][j][k].y == buf[i][j][k+1].y) continue;
				auto &[x, y, S] = buf[i][j][k];
				int pt = 0;

				while(pt<(int)FUCK[i][j].size() && !(buf[i][j][k] < FUCK[i][j][pt])){
					if (FUCK[i][j][pt].x == x && FUCK[i][j][pt].y == y) rans[FUCK[i][j][pt].sum] += S;
					pt++;
				}
			}
		}
	}

	for (int i=1;i<=q;i++) printf("%d\n", rans[i]);
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 166 ms 174064 KB Output is correct
3 Correct 164 ms 173996 KB Output is correct
4 Correct 324 ms 174240 KB Output is correct
5 Correct 335 ms 174280 KB Output is correct
6 Correct 88 ms 60604 KB Output is correct
7 Correct 87 ms 59068 KB Output is correct
8 Correct 87 ms 59088 KB Output is correct
9 Correct 85 ms 58480 KB Output is correct
10 Correct 86 ms 59364 KB Output is correct
11 Correct 89 ms 61268 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 925 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Runtime error 786 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 166 ms 174064 KB Output is correct
3 Correct 164 ms 173996 KB Output is correct
4 Correct 324 ms 174240 KB Output is correct
5 Correct 335 ms 174280 KB Output is correct
6 Correct 88 ms 60604 KB Output is correct
7 Correct 87 ms 59068 KB Output is correct
8 Correct 87 ms 59088 KB Output is correct
9 Correct 85 ms 58480 KB Output is correct
10 Correct 86 ms 59364 KB Output is correct
11 Correct 89 ms 61268 KB Output is correct
12 Runtime error 925 ms 1048576 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -