oj.uz

Submission #804471

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

unordered_map<signed long long, int> srt[70][70];

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

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

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


    register int i, j;
    register signed long long px, py;
    unordered_map<signed long long, int>::iterator p;
    register int ans, lx, ly;
    register signed long long x, y;
    for(int rep = 0; rep < q; ++rep){
        cin >> x >> y;
        
        ans = 0, lx = len(x), ly = len(y);
        for(i = 0; i < lx; ++i){
            for(j = 0; j < ly; ++j){
                if(!(int)srt[i][j].size()) continue;
                px = x % (1ll << i) + (1ll << i);
                py = y % (1ll << j) + (1ll << j);

                p = srt[i][j].find(A * px + B * py);
                if(p != srt[i][j].end()){
                    ans += p->second;
                }
            }
        }

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

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:30:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   30 |     register int i, j;
      |                  ^
Main.cpp:30:21: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   30 |     register int i, j;
      |                     ^
Main.cpp:31:31: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   31 |     register signed long long px, py;
      |                               ^~
Main.cpp:31:35: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   31 |     register signed long long px, py;
      |                                   ^~
Main.cpp:33:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   33 |     register int ans, lx, ly;
      |                  ^~~
Main.cpp:33:23: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   33 |     register int ans, lx, ly;
      |                       ^~
Main.cpp:33:27: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   33 |     register int ans, lx, ly;
      |                           ^~
Main.cpp:34:31: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   34 |     register signed long long x, y;
      |                               ^
Main.cpp:34:34: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   34 |     register signed long long x, y;
      |                                  ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 9 ms 596 KB Output is correct
3 Correct 8 ms 684 KB Output is correct
4 Correct 107 ms 816 KB Output is correct
5 Correct 110 ms 824 KB Output is correct
6 Correct 28 ms 824 KB Output is correct
7 Correct 26 ms 820 KB Output is correct
8 Correct 28 ms 828 KB Output is correct
9 Correct 25 ms 832 KB Output is correct
10 Correct 26 ms 828 KB Output is correct
11 Correct 27 ms 816 KB Output is correct

Subtask #2
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 844 ms 9812 KB Output is correct
2 Correct 969 ms 9820 KB Output is correct
3 Correct 1897 ms 9308 KB Output is correct
4 Correct 2221 ms 9304 KB Output is correct
5 Correct 713 ms 9356 KB Output is correct
6 Correct 646 ms 9304 KB Output is correct
7 Correct 827 ms 9292 KB Output is correct
8 Correct 794 ms 9228 KB Output is correct
9 Correct 781 ms 9288 KB Output is correct
10 Correct 719 ms 9392 KB Output is correct

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 596 KB Output is correct
2 Correct 225 ms 5388 KB Output is correct
3 Correct 175 ms 5496 KB Output is correct
4 Execution timed out 4011 ms 5296 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 9 ms 596 KB Output is correct
3 Correct 8 ms 684 KB Output is correct
4 Correct 107 ms 816 KB Output is correct
5 Correct 110 ms 824 KB Output is correct
6 Correct 28 ms 824 KB Output is correct
7 Correct 26 ms 820 KB Output is correct
8 Correct 28 ms 828 KB Output is correct
9 Correct 25 ms 832 KB Output is correct
10 Correct 26 ms 828 KB Output is correct
11 Correct 27 ms 816 KB Output is correct
12 Correct 844 ms 9812 KB Output is correct
13 Correct 969 ms 9820 KB Output is correct
14 Correct 1897 ms 9308 KB Output is correct
15 Correct 2221 ms 9304 KB Output is correct
16 Correct 713 ms 9356 KB Output is correct
17 Correct 646 ms 9304 KB Output is correct
18 Correct 827 ms 9292 KB Output is correct
19 Correct 794 ms 9228 KB Output is correct
20 Correct 781 ms 9288 KB Output is correct
21 Correct 719 ms 9392 KB Output is correct
22 Correct 1 ms 596 KB Output is correct
23 Correct 225 ms 5388 KB Output is correct
24 Correct 175 ms 5496 KB Output is correct
25 Execution timed out 4011 ms 5296 KB Time limit exceeded
26 Halted 0 ms 0 KB -