oj.uz

Submission #804159

# Submission time Handle Problem Language Result Execution time Memory
804159 2023-08-03T07:25:17 Z 박상훈(#10101) Vera and Modern Art (CCO17_art) C++17
0 / 25
 979 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++){
				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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 171 ms 174024 KB Output is correct
3 Correct 166 ms 174008 KB Output is correct
4 Correct 327 ms 174236 KB Output is correct
5 Correct 317 ms 174268 KB Output is correct
6 Incorrect 93 ms 60560 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 979 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 0 ms 468 KB Output is correct
2 Runtime error 787 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 0 ms 468 KB Output is correct
2 Correct 171 ms 174024 KB Output is correct
3 Correct 166 ms 174008 KB Output is correct
4 Correct 327 ms 174236 KB Output is correct
5 Correct 317 ms 174268 KB Output is correct
6 Incorrect 93 ms 60560 KB Output isn't correct
7 Halted 0 ms 0 KB -