oj.uz

Submission #803759

# Submission time Handle Problem Language Result Execution time Memory
803759 2023-08-03T05:51:11 Z 이동현(#10103) Vera and Modern Art (CCO17_art) C++17
5 / 25
 4000 ms 7828 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);
    }
};
vector<Data> srt[70][70];

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

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

    register int i, j;

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

    int n, q;
    cin >> n >> q;
    // n = q = 200000;
    for(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].push_back({x, y, v});
    }

    for(i = 0; i < 70; ++i){
        for(j = 0; j < 70; ++j){
            sort(srt[i][j].begin(), srt[i][j].end());
            for(int k = 1; k < (int)srt[i][j].size(); ++k){
                srt[i][j][k].sum += srt[i][j][k - 1].sum;
            }
        }
    }

    register int p1, p2;
    register long long x, y;
    register int ans;
    register int lx, ly;
    register long long yv;

    for(int rep = 0; rep < q; ++rep){
        cin >> x >> y;
        yv = y;
        lx = len(x) - 1, ly = len(y) - 1;
        ans = 0;
        for(i = lx; i >= 0; --i){
            if(x >= (1ll << (i + 1))) x -= 1ll << i;
            if(x >= (1ll << (i + 1))) x -= 1ll << i;

            y = yv;
            for(j = ly; j >= 0; --j){
                if(y >= (1ll << (j + 1))) y -= 1ll << j;
                if(y >= (1ll << (j + 1))) y -= 1ll << j;

                if(!(int)srt[i][j].size()) continue;

                p1 = lower_bound(srt[i][j].begin(), srt[i][j].end(), Data(x, y, -1)) - srt[i][j].begin();
                p2 = lower_bound(srt[i][j].begin(), srt[i][j].end(), Data(x, y + 1, -1)) - srt[i][j].begin() - 1;
                if(p1 <= p2){
                    ans += srt[i][j][p2].sum;
                    if(p1) ans -= srt[i][j][p1 - 1].sum;
                }
            }
        }

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

Compilation message

Main.cpp: In function 'int main()':
Main.cpp:25:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   25 |     register int i, j;
      |                  ^
Main.cpp:25:21: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   25 |     register int i, j;
      |                     ^
Main.cpp:50:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   50 |     register int p1, p2;
      |                  ^~
Main.cpp:50:22: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   50 |     register int p1, p2;
      |                      ^~
Main.cpp:51:24: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   51 |     register long long x, y;
      |                        ^
Main.cpp:51:27: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   51 |     register long long x, y;
      |                           ^
Main.cpp:52:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   52 |     register int ans;
      |                  ^~~
Main.cpp:53:18: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   53 |     register int lx, ly;
      |                  ^~
Main.cpp:53:22: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   53 |     register int lx, ly;
      |                      ^~
Main.cpp:54:24: warning: ISO C++17 does not allow 'register' storage class specifier [-Wregister]
   54 |     register long long yv;
      |                        ^~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 22 ms 544 KB Output is correct
3 Correct 22 ms 528 KB Output is correct
4 Correct 125 ms 604 KB Output is correct
5 Correct 140 ms 496 KB Output is correct
6 Correct 34 ms 508 KB Output is correct
7 Correct 34 ms 468 KB Output is correct
8 Correct 33 ms 504 KB Output is correct
9 Correct 34 ms 468 KB Output is correct
10 Correct 33 ms 504 KB Output is correct
11 Correct 34 ms 500 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2321 ms 6332 KB Output is correct
2 Correct 2345 ms 6248 KB Output is correct
3 Execution timed out 4062 ms 7828 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 440 ms 3632 KB Output is correct
3 Correct 460 ms 3660 KB Output is correct
4 Execution timed out 4051 ms 3912 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 22 ms 544 KB Output is correct
3 Correct 22 ms 528 KB Output is correct
4 Correct 125 ms 604 KB Output is correct
5 Correct 140 ms 496 KB Output is correct
6 Correct 34 ms 508 KB Output is correct
7 Correct 34 ms 468 KB Output is correct
8 Correct 33 ms 504 KB Output is correct
9 Correct 34 ms 468 KB Output is correct
10 Correct 33 ms 504 KB Output is correct
11 Correct 34 ms 500 KB Output is correct
12 Correct 2321 ms 6332 KB Output is correct
13 Correct 2345 ms 6248 KB Output is correct
14 Execution timed out 4062 ms 7828 KB Time limit exceeded
15 Halted 0 ms 0 KB -