oj.uz

Submission #804075

# Submission time Handle Problem Language Result Execution time Memory
804075 2023-08-03T07:02:35 Z 박상훈(#10101) Vera and Modern Art (CCO17_art) C++17
0 / 25
 4000 ms 321952 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

struct Node{
	int len;
	ll y;
	int idx, sum;

	Node(){}
	Node(int _len, ll _y, int _idx, int _sum): len(_len), y(_y), idx(_idx), sum(_sum) {}

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

int n, q;

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

vector<Node> V[64][200200];
vector<ll> bufx[64];
vector<pair<ll, int>> bufy[64];

int lenx[200200], leny[200200], goY[200200], chk[64][200200];
pair<int, int> goX[200200];

int target[64][200200];
pair<int, int> que[64];

void build(int s, int t){
	sort(V[s][t].begin(), V[s][t].end());
	for (int j=0;j<(int)V[s][t].size();j++){
		auto &[len, y, idx, sum] = V[s][t][j];
		// printf("calc %d %lld %d %d\n", len, y, idx, sum);

		for (int z=len;z>=0;z--){
			auto iter = upper_bound(V[s][t].begin(), V[s][t].begin()+j, Node(z, y&((1LL<<z)-1), 0, 0));
			if (iter==V[s][t].begin()) continue;
			
			--iter;
			// printf("ok %d %lld -> %d %lld\n", len, y, iter->len, iter->y);
			if (iter->len != z) continue;
			if (iter->y != (y&((1LL<<z)-1))) continue;

			sum += iter->sum;
			break;
		}

		goY[idx] = j;
	}

	chk[s][t] = 1;
}

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

		bufx[z].push_back(X[i]&((1LL<<z)-1));
		lenx[i] = z;

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

		bufy[z].emplace_back(Y[i]&((1LL<<z)-1), i);
		leny[i] = z;
	}

	for (int z=0;z<64;z++){
		sort(bufx[z].begin(), bufx[z].end());
		bufx[z].erase(unique(bufx[z].begin(), bufx[z].end()), bufx[z].end());

		sort(bufy[z].begin(), bufy[z].end());
	}

	for (int i=1;i<=n;i++){
		goX[i].first = lenx[i];
		goX[i].second = lower_bound(bufx[lenx[i]].begin(), bufx[lenx[i]].end(), X[i]&((1LL<<lenx[i])-1)) - bufx[lenx[i]].begin();

		auto [s, t] = goX[i];
		V[s][t].emplace_back(leny[i], Y[i]&((1LL<<leny[i])-1), i, a[i]);
	}

	for (int i=1;i<=n;i++){
		auto [s, t] = goX[i];
		if (chk[s][t]) continue;

		build(s, t);
	}
}

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 pt = 0, ans = 0;

		for (int i=0;(1LL<<i)<=x;i++){
			ll nx = x & ((1LL<<i)-1);
			auto iter = lower_bound(bufx[i].begin(), bufx[i].end(), nx);
			if (iter==bufx[i].end() || *iter!=nx) continue;

			que[pt++] = {i, iter-bufx[i].begin()};
			target[i][iter-bufx[i].begin()] = -1;
		}

		for (int j=0;(1LL<<j)<=y;j++){
			ll ny = y & ((1LL<<j)-1);
			auto iter = lower_bound(bufy[j].begin(), bufy[j].end(), pair<ll, int>(ny, -1));
			
			for(;iter!=bufy[j].end();iter++){
				if (iter->first!=ny) break;

				int idx = iter->second;
				auto [i1, x1] = goX[idx];
				target[i1][x1] = goY[idx];
			}
		}

		for (int i=0;i<pt;i++){
			auto [s, t] = que[i];
			if (target[s][t]==-1) continue;
			ans += V[s][t][target[s][t]].sum;
		}

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

Compilation message

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

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 301200 KB Output is correct
2 Correct 168 ms 301496 KB Output is correct
3 Correct 199 ms 301576 KB Output is correct
4 Correct 183 ms 302120 KB Output is correct
5 Correct 192 ms 302120 KB Output is correct
6 Incorrect 190 ms 302100 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4106 ms 321952 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 190 ms 301244 KB Output is correct
2 Correct 391 ms 312252 KB Output is correct
3 Correct 386 ms 312176 KB Output is correct
4 Incorrect 3629 ms 312696 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 205 ms 301200 KB Output is correct
2 Correct 168 ms 301496 KB Output is correct
3 Correct 199 ms 301576 KB Output is correct
4 Correct 183 ms 302120 KB Output is correct
5 Correct 192 ms 302120 KB Output is correct
6 Incorrect 190 ms 302100 KB Output isn't correct
7 Halted 0 ms 0 KB -