| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 804142 |
2023-08-03T07:19:58 Z |
이성호(#10102) |
Vera and Modern Art (CCO17_art) |
C++17 |
|
4000 ms |
363384 KB |
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#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;
}
};
vector<Oper> vc[2];
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].push_back(op);
Oper op2 = {p2, 0, t1, p1, 0, v}; vc[1].push_back(op2);
mp[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;
ans[i] += mp[coord[i]];
Oper op = {coord[i].first, coord[i].second, -1, 0, i};
Oper op2 = {coord[i].second, coord[i].first, -1, 0, i};
vc[0].push_back(op); vc[1].push_back(op2);
}
for (int t = 0; t < 2; t++) {
sort(vc[0].begin(), vc[0].end());
for (int i = 0; i < (int)vc[0].size(); i++) {
int s = i;
while (i + 1 < (int)vc[0].size() && 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 s = i, 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;
int e = i;
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:93:25: warning: unused variable 's' [-Wunused-variable]
93 | int s = i, cur = dsr[k][i].second;
| ^
Main.cpp:95:25: warning: unused variable 'e' [-Wunused-variable]
95 | int e = i;
| ^
Main.cpp:136: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]
136 | 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:4:
/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 |
1 ms |
852 KB |
Output is correct |
| 2 |
Correct |
57 ms |
4628 KB |
Output is correct |
| 3 |
Correct |
59 ms |
4504 KB |
Output is correct |
| 4 |
Correct |
68 ms |
4492 KB |
Output is correct |
| 5 |
Correct |
68 ms |
4624 KB |
Output is correct |
| 6 |
Correct |
49 ms |
4496 KB |
Output is correct |
| 7 |
Correct |
62 ms |
4496 KB |
Output is correct |
| 8 |
Correct |
52 ms |
4496 KB |
Output is correct |
| 9 |
Correct |
50 ms |
4504 KB |
Output is correct |
| 10 |
Correct |
50 ms |
4504 KB |
Output is correct |
| 11 |
Correct |
60 ms |
4496 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
4059 ms |
363384 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
852 KB |
Output is correct |
| 2 |
Correct |
2215 ms |
178740 KB |
Output is correct |
| 3 |
Correct |
2105 ms |
178720 KB |
Output is correct |
| 4 |
Correct |
2467 ms |
180784 KB |
Output is correct |
| 5 |
Correct |
2432 ms |
180788 KB |
Output is correct |
| 6 |
Correct |
1962 ms |
180684 KB |
Output is correct |
| 7 |
Correct |
1968 ms |
180660 KB |
Output is correct |
| 8 |
Correct |
1927 ms |
180652 KB |
Output is correct |
| 9 |
Correct |
1874 ms |
180712 KB |
Output is correct |
| 10 |
Correct |
1883 ms |
180704 KB |
Output is correct |
| 11 |
Correct |
1910 ms |
180560 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
852 KB |
Output is correct |
| 2 |
Correct |
57 ms |
4628 KB |
Output is correct |
| 3 |
Correct |
59 ms |
4504 KB |
Output is correct |
| 4 |
Correct |
68 ms |
4492 KB |
Output is correct |
| 5 |
Correct |
68 ms |
4624 KB |
Output is correct |
| 6 |
Correct |
49 ms |
4496 KB |
Output is correct |
| 7 |
Correct |
62 ms |
4496 KB |
Output is correct |
| 8 |
Correct |
52 ms |
4496 KB |
Output is correct |
| 9 |
Correct |
50 ms |
4504 KB |
Output is correct |
| 10 |
Correct |
50 ms |
4504 KB |
Output is correct |
| 11 |
Correct |
60 ms |
4496 KB |
Output is correct |
| 12 |
Execution timed out |
4059 ms |
363384 KB |
Time limit exceeded |
| 13 |
Halted |
0 ms |
0 KB |
- |
