oj.uz

Submission #803902

# Submission time Handle Problem Language Result Execution time Memory
803902 2023-08-03T06:29:29 Z 이성호(#10102) Vera and Modern Art (CCO17_art) C++17
5 / 25
 4000 ms 495508 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> xc[bit], yc[bit], 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;
}
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];
        mp[make_pair(p1, p2)] += v;
        yc[t1][make_pair(p1, p2)] += v;
        xc[t2][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]];
        for (int j = 0; j < bit; j++) {
            ans[i] -= xc[j][make_pair(coord[i].first, coord[i].second%mul[j])];
            ans[i] -= yc[j][make_pair(coord[i].first%mul[j], coord[i].second)];
        }
    }
    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:77: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]
   77 |         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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 97 ms 14812 KB Output is correct
3 Correct 108 ms 15052 KB Output is correct
4 Correct 147 ms 19400 KB Output is correct
5 Correct 151 ms 19280 KB Output is correct
6 Correct 118 ms 19320 KB Output is correct
7 Correct 114 ms 19272 KB Output is correct
8 Correct 125 ms 19300 KB Output is correct
9 Correct 127 ms 19312 KB Output is correct
10 Correct 110 ms 19316 KB Output is correct
11 Correct 124 ms 19328 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4090 ms 352908 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Execution timed out 4097 ms 495508 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 852 KB Output is correct
2 Correct 97 ms 14812 KB Output is correct
3 Correct 108 ms 15052 KB Output is correct
4 Correct 147 ms 19400 KB Output is correct
5 Correct 151 ms 19280 KB Output is correct
6 Correct 118 ms 19320 KB Output is correct
7 Correct 114 ms 19272 KB Output is correct
8 Correct 125 ms 19300 KB Output is correct
9 Correct 127 ms 19312 KB Output is correct
10 Correct 110 ms 19316 KB Output is correct
11 Correct 124 ms 19328 KB Output is correct
12 Execution timed out 4090 ms 352908 KB Time limit exceeded
13 Halted 0 ms 0 KB -