| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 804232 |
2023-08-03T07:37:08 Z |
이성호(#10102) |
Vera and Modern Art (CCO17_art) |
C++17 |
|
4000 ms |
345132 KB |
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
using ll = long long;
const int bit = 60;
ll mul[bit+1] = {1};
int N, Q, ans[200005];
map<pair<ll, ll>, int> mp;
vector<pair<pair<ll, ll>, int>> sc[bit][bit];
pair<ll, ll> coord[200005];
pair<pair<ll, ll>, int> sorted[bit][200005];
pair<pair<ll, ll>, int> tmp[200005];
inline int lg2(ll x)
{
int i = 0;
while (1LL << (i+1) <= x) i++;
return i;
}
struct Oper
{
ll x, y;
ll id, r, idx, val;
bool operator<(const Oper &op) const {
return x < op.x;
}
};
Oper vc[2][400005];
int pt[2];
pair<pair<ll, ll>, int> co[200005], nd[200005];
int main()
{
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
for (int i = 1; i <= bit; i++) mul[i] = mul[i-1] << 1;
cin >> N >> Q;
for (int i = 0; i < N; i++) {
ll r, c; int v; cin >> r >> c >> v;
int t1 = lg2(r), t2 = lg2(c);
ll p1 = r % mul[t1], p2 = c % mul[t2];
Oper op = {p1, 0, t2, p2, 0, v}; vc[0][pt[0]++] = op;
Oper op2 = {p2, 0, t1, p1, 0, v}; vc[1][pt[1]++] = op2;
co[i] = make_pair(make_pair(p1, p2), v);
sc[t2][t1].push_back(make_pair(make_pair(p1, p2), v));
}
for (int i = 0; i < Q; i++) {
cin >> coord[i].first >> coord[i].second;
nd[i] = make_pair(coord[i], i);
Oper op = {coord[i].first, coord[i].second, -1, 0, i}; vc[0][pt[0]++] = op;
Oper op2 = {coord[i].second, coord[i].first, -1, 0, i}; vc[1][pt[1]++] = op2;
}
sort(co, co + N); sort(nd, nd + Q);
int point = 0;
for (int i = 0; i < N; i++) {
int cur = co[i].second;
while (i + 1 < N && co[i].first == co[i+1].first) cur += co[++i].second;
while (point < Q && nd[point].first < co[i].first) point++;
while (point < Q && nd[point].first == co[i].first) ans[nd[point++].second] += cur;
}
for (int t = 0; t < 2; t++) {
sort(vc[0], vc[0] + pt[t]);
for (int i = 0; i < pt[t]; i++) {
int s = i;
while (i + 1 < pt[t] && vc[0][i].x == vc[0][i+1].x) i++;
int e = i;
vector<pair<ll, int>> dsr[60];
vector<pair<ll, int>> coords, tmp;
for (int j = s; j <= e; j++) {
if (vc[0][j].id != -1) dsr[vc[0][j].id].push_back(make_pair(vc[0][j].r, vc[0][j].val));
else coords.push_back(make_pair(vc[0][j].y, vc[0][j].idx));
}
sort(coords.begin(), coords.end());
for (int k = 59; k >= 0; k--) {
sort(dsr[k].begin(), dsr[k].end());
int id = (int)coords.size();
for (int p = (int)coords.size() - 1; p >= 0; p--) {
if (coords[p].first >= mul[k]) id = p;
else break;
}
int p1 = 0, p2 = id;
while (p1 < id || p2 < (int)coords.size()) {
bool choose = false;
if (p1 == id) choose = true;
else if (p2 == (int)coords.size()) choose = false;
else if (coords[p1].first < coords[p2].first - mul[k]) choose = false;
else choose = true;
if (!choose) {
tmp.push_back(coords[p1++]);
}
else {
tmp.push_back(make_pair(coords[p2].first - mul[k], coords[p2].second));
p2++;
}
}
swap(coords, tmp); tmp.clear();
int point = 0;
for (int i = 0; i < (int)dsr[k].size(); i++) {
int cur = dsr[k][i].second;
while (i + 1 < (int)dsr[k].size() && dsr[k][i].first == dsr[k][i+1].first) cur += dsr[k][++i].second;
while (point < (int)coords.size() && coords[point].first < dsr[k][i].first) point++;
while (point < (int)coords.size() && coords[point].first == dsr[k][i].first) ans[coords[point++].second] -= cur;
}
}
}
swap(vc[0], vc[1]);
}
for (int i = 0; i < bit; i++) {
for (int j = 0; j < bit; j++) {
sort(sc[i][j].begin(), sc[i][j].end());
}
}
for (int i = 0; i < Q; i++) sorted[bit-1][i] = make_pair(make_pair(coord[i].first % mul[bit-1], coord[i].second), i);
sort(sorted[bit-1], sorted[bit-1] + Q);
for (int t = bit-1; t >= 0; t--) {
int pv = 0;
for (int i = 0; i < Q; i++) {
int s = i;
while (i + 1 < Q && sorted[bit-1][i].first.first == sorted[bit-1][i+1].first.first) i++;
int e = i;
int p1 = s, p2 = s;
while (p2 <= e && sorted[bit-1][p2].first.second < mul[t]) p2++;
int lst = p2;
while (p1 < lst || p2 <= e) {
if (p1 == lst) {
tmp[pv] = sorted[bit-1][p2++];
tmp[pv++].first.second -= mul[t];
}
else if (p2 == e + 1) {
tmp[pv++] = sorted[bit-1][p1++];
}
else if (sorted[bit-1][p1].first.second < sorted[bit-1][p2].first.second - mul[t]) {
tmp[pv++] = sorted[bit-1][p1++];
}
else {
tmp[pv] = sorted[bit-1][p2++];
tmp[pv++].first.second -= mul[t];
}
}
}
memcpy(sorted[bit-1], tmp, sizeof(pair<pair<ll, ll>, int>) * Q);
for (int j = bit-1; j >= 0; j--) {
int point = 0;
for (int k = 0; k < (int)sc[t][j].size(); k++) {
int val = sc[t][j][k].second;
while (k + 1 < (int)sc[t][j].size() && sc[t][j][k].first == sc[t][j][k+1].first) val += sc[t][j][++k].second;
while (point < Q && sorted[j][point].first < sc[t][j][k].first) point++;
while (point < Q && sorted[j][point].first == sc[t][j][k].first) ans[sorted[j][point++].second] += val;
}
if (j == 0) break;
int id = Q;
for (int i = Q - 1; i >= 0; i--) {
if (sorted[j][i].first.first >= mul[j-1]) id = i;
else break;
}
int p1 = 0, p2 = id, pv = 0;
while (p1 < id || p2 < Q) {
bool choose = false;
if (p1 == id) choose = true;
else if (p2 == Q) choose = false;
else if (sorted[j][p1].first < make_pair(sorted[j][p2].first.first - mul[j-1], sorted[j][p2].first.second)) choose = false;
else choose = true;
if (!choose) {
sorted[j-1][pv++] = sorted[j][p1++];
}
else {
sorted[j-1][pv] = sorted[j][p2++];
sorted[j-1][pv++].first.first -= mul[j-1];
}
}
}
}
for (int i = 0; i < Q; i++) {
cout << ans[i] << '\n';
}
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:141:71: warning: 'void* memcpy(void*, const void*, size_t)' writing to an object of type 'struct std::pair<std::pair<long long int, long long int>, int>' with no trivial copy-assignment; use copy-assignment or copy-initialization instead [-Wclass-memaccess]
141 | memcpy(sorted[bit-1], tmp, sizeof(pair<pair<ll, ll>, int>) * Q);
| ^
In file included from /usr/include/c++/10/bits/stl_algobase.h:64,
from /usr/include/c++/10/bits/char_traits.h:39,
from /usr/include/c++/10/ios:40,
from /usr/include/c++/10/ostream:38,
from /usr/include/c++/10/iostream:39,
from Main.cpp:1:
/usr/include/c++/10/bits/stl_pair.h:211:12: note: 'struct std::pair<std::pair<long long int, long long int>, int>' declared here
211 | struct pair
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
38380 KB |
Output is correct |
| 2 |
Correct |
80 ms |
41564 KB |
Output is correct |
| 3 |
Correct |
80 ms |
41496 KB |
Output is correct |
| 4 |
Correct |
114 ms |
41540 KB |
Output is correct |
| 5 |
Correct |
110 ms |
41544 KB |
Output is correct |
| 6 |
Correct |
70 ms |
41524 KB |
Output is correct |
| 7 |
Correct |
73 ms |
41560 KB |
Output is correct |
| 8 |
Correct |
89 ms |
41476 KB |
Output is correct |
| 9 |
Correct |
88 ms |
41540 KB |
Output is correct |
| 10 |
Correct |
82 ms |
41532 KB |
Output is correct |
| 11 |
Correct |
76 ms |
41548 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4059 ms |
345132 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
26 ms |
38392 KB |
Output is correct |
| 2 |
Correct |
2019 ms |
191540 KB |
Output is correct |
| 3 |
Correct |
2088 ms |
191696 KB |
Output is correct |
| 4 |
Correct |
2361 ms |
192460 KB |
Output is correct |
| 5 |
Correct |
2323 ms |
192536 KB |
Output is correct |
| 6 |
Correct |
1941 ms |
192552 KB |
Output is correct |
| 7 |
Correct |
1954 ms |
192540 KB |
Output is correct |
| 8 |
Correct |
1862 ms |
192492 KB |
Output is correct |
| 9 |
Correct |
1957 ms |
192564 KB |
Output is correct |
| 10 |
Correct |
1986 ms |
192572 KB |
Output is correct |
| 11 |
Correct |
1901 ms |
192508 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
32 ms |
38380 KB |
Output is correct |
| 2 |
Correct |
80 ms |
41564 KB |
Output is correct |
| 3 |
Correct |
80 ms |
41496 KB |
Output is correct |
| 4 |
Correct |
114 ms |
41540 KB |
Output is correct |
| 5 |
Correct |
110 ms |
41544 KB |
Output is correct |
| 6 |
Correct |
70 ms |
41524 KB |
Output is correct |
| 7 |
Correct |
73 ms |
41560 KB |
Output is correct |
| 8 |
Correct |
89 ms |
41476 KB |
Output is correct |
| 9 |
Correct |
88 ms |
41540 KB |
Output is correct |
| 10 |
Correct |
82 ms |
41532 KB |
Output is correct |
| 11 |
Correct |
76 ms |
41548 KB |
Output is correct |
| 12 |
Execution timed out |
4059 ms |
345132 KB |
Time limit exceeded |
| 13 |
Halted |
0 ms |
0 KB |
- |
