oj.uz

Submission #803991

# Submission time Handle Problem Language Result Execution time Memory
803991 2023-08-03T06:48:08 Z 박영우(#10104) Vera and Modern Art (CCO17_art) C++17
10 / 25
 1620 ms 59852 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 6010101
#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;
	int 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, j;
		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;
      |        ~~~~^~~~~~~~~~~~~
Main.cpp:58:10: warning: unused variable 'j' [-Wunused-variable]
   58 |   int i, j;
      |          ^

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 7 ms 2516 KB Output is correct
3 Correct 7 ms 2516 KB Output is correct
4 Incorrect 12 ms 1492 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 455 ms 26628 KB Output is correct
2 Correct 502 ms 26588 KB Output is correct
3 Correct 1620 ms 22500 KB Output is correct
4 Correct 1547 ms 22624 KB Output is correct
5 Correct 778 ms 22584 KB Output is correct
6 Correct 772 ms 22624 KB Output is correct
7 Correct 822 ms 22588 KB Output is correct
8 Correct 797 ms 22576 KB Output is correct
9 Correct 798 ms 22656 KB Output is correct
10 Correct 781 ms 22568 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 253 ms 59020 KB Output is correct
3 Correct 225 ms 59852 KB Output is correct
4 Correct 538 ms 32876 KB Output is correct
5 Correct 589 ms 33212 KB Output is correct
6 Correct 346 ms 33060 KB Output is correct
7 Correct 300 ms 32956 KB Output is correct
8 Correct 276 ms 33032 KB Output is correct
9 Correct 281 ms 33028 KB Output is correct
10 Correct 307 ms 33092 KB Output is correct
11 Correct 301 ms 33052 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 7 ms 2516 KB Output is correct
3 Correct 7 ms 2516 KB Output is correct
4 Incorrect 12 ms 1492 KB Output isn't correct
5 Halted 0 ms 0 KB -