답안 #804250

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
804250 2023-08-03T07:40:34 Z 이성호(#10102) Vera and Modern Art (CCO17_art) C++17
5 / 25
1008 ms 346960 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 % 2), i);
    sort(sorted[bit-1], sorted[bit-1] + Q);
    for (int t = 0; 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
      |            ^~~~
# 결과 실행 시간 메모리 Grader output
1 Incorrect 25 ms 38484 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Correct 833 ms 346824 KB Output is correct
2 Correct 871 ms 346960 KB Output is correct
3 Correct 861 ms 345564 KB Output is correct
4 Correct 1008 ms 345684 KB Output is correct
5 Correct 730 ms 345416 KB Output is correct
6 Correct 730 ms 345660 KB Output is correct
7 Correct 762 ms 345552 KB Output is correct
8 Correct 762 ms 345764 KB Output is correct
9 Correct 733 ms 345436 KB Output is correct
10 Correct 732 ms 345332 KB Output is correct
# 결과 실행 시간 메모리 Grader output
1 Incorrect 34 ms 38484 KB Output isn't correct
2 Halted 0 ms 0 KB -
# 결과 실행 시간 메모리 Grader output
1 Incorrect 25 ms 38484 KB Output isn't correct
2 Halted 0 ms 0 KB -