oj.uz

Submission #803398

# Submission time Handle Problem Language Result Execution time Memory
803398 2023-08-03T04:23:37 Z DK 아즈버지비우(#10138) Vera and Modern Art (CCO17_art) C++17
5 / 25
 3908 ms 1048576 KB 
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pdd pair<long double, long double>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define ppi pair<pii, pii>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
typedef long long ll;
using namespace std;
const int mxN=300020;
const int mxM=63;
const int MOD=1e9+7;
const ll INF=1e18;
int N, Q;
map <pll, ll> mp1, mpx[mxM], mpy[mxM], mpxy[mxM][mxM];
void input()
{
    cin >> N >> Q;
    for(int i=1;i<=N;i++)
    {
        ll x, y, v;
        cin >> x >> y >> v;
        ll px=1, py=1, ix=0, iy=0;
        while(2*px<=x)  px*=2, ix++;
        while(2*py<=y)  py*=2, iy++;
        x-=px;  y-=py;
        mp1[pll(x, y)]+=v;
        mpx[ix][pll(x, y)]-=v;
        mpy[iy][pll(x, y)]-=v;
        mpxy[ix][iy][pll(x, y)]+=v;
    }
    for(int i=0;i<Q;i++)
    {
        ll x, y;
        cin >> x >> y;
        ll res=0;
        res+=mp1[pll(x, y)];
        for(int j=0;j<60;j++)   res+=mpx[j][pll(x%(1ll<<j), y)];
        for(int j=0;j<60;j++)   res+=mpy[j][pll(x, y%(1ll<<j))];
        for(int j=0;j<60;j++)   for(int k=0;k<60;k++)   res+=mpxy[j][k][pll(x%(1ll<<j), y%(1ll<<k))];
        cout << res << '\n';
    }
}
int main()
{
    gibon
    input();
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1876 KB Output is correct
2 Correct 1572 ms 291476 KB Output is correct
3 Correct 1650 ms 291972 KB Output is correct
4 Correct 3181 ms 458400 KB Output is correct
5 Correct 3020 ms 458464 KB Output is correct
6 Correct 2586 ms 454824 KB Output is correct
7 Correct 2594 ms 454988 KB Output is correct
8 Correct 2516 ms 454904 KB Output is correct
9 Correct 2785 ms 454548 KB Output is correct
10 Correct 2564 ms 455096 KB Output is correct
11 Correct 2593 ms 455168 KB Output is correct

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 3908 ms 1048576 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1876 KB Output is correct
2 Runtime error 2664 ms 1048576 KB Execution killed with signal 9
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1876 KB Output is correct
2 Correct 1572 ms 291476 KB Output is correct
3 Correct 1650 ms 291972 KB Output is correct
4 Correct 3181 ms 458400 KB Output is correct
5 Correct 3020 ms 458464 KB Output is correct
6 Correct 2586 ms 454824 KB Output is correct
7 Correct 2594 ms 454988 KB Output is correct
8 Correct 2516 ms 454904 KB Output is correct
9 Correct 2785 ms 454548 KB Output is correct
10 Correct 2564 ms 455096 KB Output is correct
11 Correct 2593 ms 455168 KB Output is correct
12 Runtime error 3908 ms 1048576 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -