oj.uz

Submission #803792

# Submission time Handle Problem Language Result Execution time Memory
803792 2023-08-03T06:04:22 Z 이동현(#10103) Vera and Modern Art (CCO17_art) C++17
5 / 25
 4000 ms 333368 KB 
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
using namespace std;

struct Data{
    long long x, y;
    int sum;
    Data(long long x, long long y, int sum):x(x), y(y), sum(sum){}
    bool operator<(const Data&r)const{
        return x < r.x || (x == r.x && y < r.y);
    }
};
unordered_map<long long, int> srt[70][70];

signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    auto len = [&](long long x){
        return 64 - __builtin_clzll(x);
    };

    mt19937 gen(23523);
    uniform_int_distribution<long long> uid(1, (long long)1e18);

    int n, q;
    cin >> n >> q;
    long long A = 998244353;
    long long B = (int)1e9 + 7;
    // n = q = 200000;
    for(int i = 0; i < n; ++i){
        long long x, y;
        int v;
        cin >> x >> y >> v;
        // x = uid(gen), y = uid(gen), v = uid(gen);
        srt[len(x) - 1][len(y) - 1][A * x + B * y] += v;
    }

    for(int rep = 0; rep < q; ++rep){
        long long x, y;
        cin >> x >> y;
        int ans = 0;
        for(int i = 0; (1ll << i) <= x; ++i){
            for(int j = 0; (1ll << j) <= y; ++j){
                if(!(int)srt[i][j].size()) continue;
                long long px = x % (1ll << i) + (1ll << i);
                long long py = y % (1ll << j) + (1ll << j);
                
                ans += srt[i][j][A * px + B * py];
            }
        }

        cout << ans << '\n';
    }
    
    return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 11 ms 852 KB Output is correct
3 Correct 12 ms 724 KB Output is correct
4 Correct 1540 ms 122048 KB Output is correct
5 Correct 1530 ms 122124 KB Output is correct
6 Correct 264 ms 33176 KB Output is correct
7 Correct 260 ms 33840 KB Output is correct
8 Correct 313 ms 32844 KB Output is correct
9 Correct 273 ms 32216 KB Output is correct
10 Correct 310 ms 32532 KB Output is correct
11 Correct 304 ms 33680 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1142 ms 14064 KB Output is correct
2 Correct 1162 ms 14040 KB Output is correct
3 Execution timed out 4054 ms 236904 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 468 KB Output is correct
2 Correct 198 ms 12284 KB Output is correct
3 Correct 189 ms 12244 KB Output is correct
4 Execution timed out 4066 ms 333368 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 11 ms 852 KB Output is correct
3 Correct 12 ms 724 KB Output is correct
4 Correct 1540 ms 122048 KB Output is correct
5 Correct 1530 ms 122124 KB Output is correct
6 Correct 264 ms 33176 KB Output is correct
7 Correct 260 ms 33840 KB Output is correct
8 Correct 313 ms 32844 KB Output is correct
9 Correct 273 ms 32216 KB Output is correct
10 Correct 310 ms 32532 KB Output is correct
11 Correct 304 ms 33680 KB Output is correct
12 Correct 1142 ms 14064 KB Output is correct
13 Correct 1162 ms 14040 KB Output is correct
14 Execution timed out 4054 ms 236904 KB Time limit exceeded
15 Halted 0 ms 0 KB -