oj.uz

Submission #804037

# Submission time Handle Problem Language Result Execution time Memory
804037 2023-08-03T06:55:46 Z 박영우(#10104) Vera and Modern Art (CCO17_art) C++17
25 / 25
 2318 ms 211604 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 15010101
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define MOD 1000000007
ll sum[MAX];
int ch[2][MAX];
int cnt = 0;
void upd(int n, ll x, ll v) {
	if (!x) {
		sum[n] += v;
		return;
	}
	int c = x & 1;
	if (!ch[c][n]) ch[c][n] = ++cnt;
	upd(ch[c][n], x >> 1ll, v);
}
ll get(int n, ll x) {
	if (!n) return 0;
	if (!x) return 0;
	int c = x & 1;
	return sum[ch[1][n]] + get(ch[c][n], x >> 1ll);
}
signed main() {
	ios::sync_with_stdio(false), cin.tie(0);
	int N, Q;
	cin >> N >> Q;
	int i;
	ll a, b, c;
	map<pll, ll> mp;
	for (i = 1; i <= N; i++) {
		cin >> a >> b >> c;
		mp[pll(a, b)] += c;
	}
	vector<pair<pll, ll>> v;
	vector<ll> xst;
	vector<int> sind;
	ll pv = -1;
	for (auto& [a, b] : mp) {
		if (pv != a.first) {
			pv = a.first;
			cnt++;
			sind.push_back(cnt);
			xst.push_back(a.first);
		}
		upd(sind.back(), a.second, b);
		v.emplace_back(a, b);
	}
	while (Q--) {
		cin >> a >> b;
		int i;
		ll sum = 0;
		for (i = 0; i <= 62; i++) {
			if (a < (1ll << i)) break;
			ll x, mi;
			mi = (1ll << i) - 1;
			x = a & mi;
			x += mi + 1;
			int ind = lower_bound(xst.begin(), xst.end(), x) - xst.begin();
			if (ind == xst.size() || xst[ind] != x) continue;
			sum += get(sind[ind], b);
		}
		cout << sum << Ln;
	}
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:67:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |    if (ind == xst.size() || xst[ind] != x) continue;
      |        ~~~~^~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 5 ms 2388 KB Output is correct
3 Correct 5 ms 2468 KB Output is correct
4 Correct 10 ms 1492 KB Output is correct
5 Correct 9 ms 1492 KB Output is correct
6 Correct 6 ms 1492 KB Output is correct
7 Correct 8 ms 1492 KB Output is correct
8 Correct 8 ms 1492 KB Output is correct
9 Correct 6 ms 1544 KB Output is correct
10 Correct 5 ms 1492 KB Output is correct
11 Correct 6 ms 1568 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 631 ms 26580 KB Output is correct
2 Correct 549 ms 26588 KB Output is correct
3 Correct 1678 ms 22468 KB Output is correct
4 Correct 1681 ms 22608 KB Output is correct
5 Correct 800 ms 22572 KB Output is correct
6 Correct 831 ms 22584 KB Output is correct
7 Correct 802 ms 22604 KB Output is correct
8 Correct 790 ms 22580 KB Output is correct
9 Correct 798 ms 22616 KB Output is correct
10 Correct 816 ms 22620 KB Output is correct

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 252 ms 59016 KB Output is correct
3 Correct 224 ms 59848 KB Output is correct
4 Correct 530 ms 32836 KB Output is correct
5 Correct 589 ms 32912 KB Output is correct
6 Correct 318 ms 33148 KB Output is correct
7 Correct 290 ms 33048 KB Output is correct
8 Correct 287 ms 33108 KB Output is correct
9 Correct 286 ms 33064 KB Output is correct
10 Correct 322 ms 32972 KB Output is correct
11 Correct 298 ms 32968 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 5 ms 2388 KB Output is correct
3 Correct 5 ms 2468 KB Output is correct
4 Correct 10 ms 1492 KB Output is correct
5 Correct 9 ms 1492 KB Output is correct
6 Correct 6 ms 1492 KB Output is correct
7 Correct 8 ms 1492 KB Output is correct
8 Correct 8 ms 1492 KB Output is correct
9 Correct 6 ms 1544 KB Output is correct
10 Correct 5 ms 1492 KB Output is correct
11 Correct 6 ms 1568 KB Output is correct
12 Correct 631 ms 26580 KB Output is correct
13 Correct 549 ms 26588 KB Output is correct
14 Correct 1678 ms 22468 KB Output is correct
15 Correct 1681 ms 22608 KB Output is correct
16 Correct 800 ms 22572 KB Output is correct
17 Correct 831 ms 22584 KB Output is correct
18 Correct 802 ms 22604 KB Output is correct
19 Correct 790 ms 22580 KB Output is correct
20 Correct 798 ms 22616 KB Output is correct
21 Correct 816 ms 22620 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 252 ms 59016 KB Output is correct
24 Correct 224 ms 59848 KB Output is correct
25 Correct 530 ms 32836 KB Output is correct
26 Correct 589 ms 32912 KB Output is correct
27 Correct 318 ms 33148 KB Output is correct
28 Correct 290 ms 33048 KB Output is correct
29 Correct 287 ms 33108 KB Output is correct
30 Correct 286 ms 33064 KB Output is correct
31 Correct 322 ms 32972 KB Output is correct
32 Correct 298 ms 32968 KB Output is correct
33 Correct 739 ms 211604 KB Output is correct
34 Correct 705 ms 211604 KB Output is correct
35 Correct 2268 ms 117716 KB Output is correct
36 Correct 2318 ms 117796 KB Output is correct
37 Correct 1221 ms 118064 KB Output is correct
38 Correct 1174 ms 118052 KB Output is correct
39 Correct 1234 ms 118000 KB Output is correct
40 Correct 1283 ms 117920 KB Output is correct
41 Correct 1178 ms 118052 KB Output is correct
42 Correct 1174 ms 117744 KB Output is correct