oj.uz

Submission #803979

# Submission time Handle Problem Language Result Execution time Memory
803979 2023-08-03T06:46:38 Z 박영우(#10104) Vera and Modern Art (CCO17_art) C++17
5 / 25
 1592 ms 48132 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 1010101
#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 5 ms 2516 KB Output is correct
3 Correct 4 ms 2388 KB Output is correct
4 Incorrect 9 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 410 ms 26544 KB Output is correct
2 Correct 473 ms 26564 KB Output is correct
3 Correct 1592 ms 22440 KB Output is correct
4 Correct 1579 ms 22568 KB Output is correct
5 Correct 767 ms 22628 KB Output is correct
6 Correct 839 ms 22588 KB Output is correct
7 Correct 781 ms 22540 KB Output is correct
8 Correct 835 ms 22620 KB Output is correct
9 Correct 789 ms 22692 KB Output is correct
10 Correct 804 ms 22648 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Runtime error 80 ms 48132 KB Execution killed with signal 11
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

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