oj.uz

Submission #803873

# Submission time Handle Problem Language Result Execution time Memory
803873 2023-08-03T06:22:16 Z 이성호(#10102) Vera and Modern Art (CCO17_art) C++17
0 / 25
 4000 ms 367880 KB 
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
using ll = long long;
const int bit = 30;
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 (1 << (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) 
            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
0 / 5.0

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

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4069 ms 344 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 596 KB Output is correct
2 Execution timed out 4062 ms 367880 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 596 KB Output is correct
2 Execution timed out 4082 ms 340 KB Time limit exceeded
3 Halted 0 ms 0 KB -