oj.uz

답안 #804232

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
804232 2023-08-03T07:37:08 Z 이성호(#10102) Vera and Modern Art (CCO17_art) C++17
10 / 25
 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
      |            ^~~~

Subtask #1
5.0 / 5.0

# 결과 실행 시간 메모리 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

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4059 ms 345132 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
5.0 / 5.0

# 결과 실행 시간 메모리 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

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 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 -