oj.uz

Submission #803854

# Submission time Handle Problem Language Result Execution time Memory
803854 2023-08-03T06:18:14 Z 이성호(#10102) Vera and Modern Art (CCO17_art) C++17
0 / 25
 4000 ms 482572 KB 
#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
#include <cstring>
using namespace std;
using ll = long long;
ll mul[61] = {1};
int N, Q, ans[200005];
map<pair<ll, ll>, int> xc[60], yc[60], mp;
vector<pair<pair<ll, ll>, int>> sc[60][60];
pair<ll, ll> coord[200005];
pair<pair<ll, ll>, int> sorted[60][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 <= 60; 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 < 60; 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 < 60; i++) {
        for (int j = 0; j < 60; j++) {
            sort(sc[i][j].begin(), sc[i][j].end());
        }
    }
    for (int i = 0; i < Q; i++) sorted[59][i] = make_pair(make_pair(coord[i].first % mul[59], coord[i].second), i);
    sort(sorted[59], sorted[59] + Q);
    for (int t = 59; t >= 0; t--) {
        int pv = 0;
        for (int i = 0; i < Q; i++) {
            int s = i;
            while (i + 1 < Q && sorted[59][i].first.first == sorted[59][i+1].first.first) i++;
            int e = i;
            int p1 = s, p2 = s;
            while (p2 <= e && sorted[59][p2].first.second < mul[t]) p2++;
            int lst = p2;
            while (p1 < lst || p2 <= e) {
                if (p1 == lst) {
                    tmp[pv] = sorted[59][p2++];
                    tmp[pv++].first.second -= mul[t];
                }
                else if (p2 == e + 1) {
                    tmp[pv++] = sorted[59][p1++];
                }
                else if (sorted[59][p1].first.second < sorted[59][p2].first.second - mul[t]) {
                    tmp[pv++] = sorted[59][p1++];
                }
                else {
                    tmp[pv] = sorted[59][p2++];
                    tmp[pv++].first.second -= mul[t];
                }
            }
        }
        memcpy(sorted[59], tmp, sizeof(pair<pair<ll, ll>, int>) * Q);
        for (int j = 59; 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:76:68: 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]
   76 |         memcpy(sorted[59], 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 852 KB Output is correct
2 Execution timed out 4059 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 4051 ms 340 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 4075 ms 482572 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 Execution timed out 4059 ms 340 KB Time limit exceeded
3 Halted 0 ms 0 KB -