oj.uz

Submission #803928

# Submission time Handle Problem Language Result Execution time Memory
803928 2023-08-03T06:36:04 Z 박영우(#10104) Vera and Modern Art (CCO17_art) C++17
10 / 25
 4000 ms 22100 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
#define MAX 110
#define MAXS 20
#define INF 1000000000000000001
#define bb ' '
#define ln '\n'
#define Ln '\n'
#define MOD 1000000007
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;
	vector<ll> xst;
	for (i = 1; i <= N; i++) {
		cin >> a >> b >> c;
		xst.push_back(a);
		mp[pll(a, b)] += c;
	}
	sort(xst.begin(), xst.end());
	vector<pair<pll, ll>> v;
	for (auto& [a, b] : mp) 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;
			for (j = 0; j <= 62; j++) {
				if (b < (1ll << j)) continue;
				ll mj, y;
				mj = (1ll << j) - 1;
				y = b & mj;
				y += mj + 1;
				int ind = lower_bound(v.begin(), v.end(), pair<pll, ll>(pll(x, y), 0)) - v.begin();
				if (ind < v.size() && v[ind].first == pll(x, y)) sum += v[ind].second;
			}
		}
		cout << sum << Ln;
	}
}

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:40:12: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   40 |    if (ind == xst.size() || xst[ind] != x) continue;
      |        ~~~~^~~~~~~~~~~~~
Main.cpp:48:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<long long int, long long int>, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     if (ind < v.size() && v[ind].first == pll(x, y)) sum += v[ind].second;
      |         ~~~~^~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 7 ms 580 KB Output is correct
3 Correct 6 ms 468 KB Output is correct
4 Correct 31 ms 468 KB Output is correct
5 Correct 28 ms 568 KB Output is correct
6 Correct 17 ms 468 KB Output is correct
7 Correct 15 ms 572 KB Output is correct
8 Correct 16 ms 556 KB Output is correct
9 Correct 16 ms 468 KB Output is correct
10 Correct 20 ms 468 KB Output is correct
11 Correct 14 ms 468 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 902 ms 22092 KB Output is correct
2 Correct 880 ms 22100 KB Output is correct
3 Execution timed out 4051 ms 19508 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 295 ms 11136 KB Output is correct
3 Correct 288 ms 11132 KB Output is correct
4 Correct 3580 ms 11000 KB Output is correct
5 Correct 3576 ms 10968 KB Output is correct
6 Correct 1632 ms 11004 KB Output is correct
7 Correct 1558 ms 10904 KB Output is correct
8 Correct 1634 ms 11044 KB Output is correct
9 Correct 1603 ms 11000 KB Output is correct
10 Correct 1678 ms 10972 KB Output is correct
11 Correct 1572 ms 10984 KB Output is correct

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 7 ms 580 KB Output is correct
3 Correct 6 ms 468 KB Output is correct
4 Correct 31 ms 468 KB Output is correct
5 Correct 28 ms 568 KB Output is correct
6 Correct 17 ms 468 KB Output is correct
7 Correct 15 ms 572 KB Output is correct
8 Correct 16 ms 556 KB Output is correct
9 Correct 16 ms 468 KB Output is correct
10 Correct 20 ms 468 KB Output is correct
11 Correct 14 ms 468 KB Output is correct
12 Correct 902 ms 22092 KB Output is correct
13 Correct 880 ms 22100 KB Output is correct
14 Execution timed out 4051 ms 19508 KB Time limit exceeded
15 Halted 0 ms 0 KB -