oj.uz

답안 #803426

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
803426 2023-08-03T04:27:52 Z DK 아즈버지비우(#10138) Vera and Modern Art (CCO17_art) C++17
5 / 25
 4000 ms 54180 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++)   if(mpx[j].count(pll(x%(1ll<<j), y)))   res+=mpx[j][pll(x%(1ll<<j), y)];
        for(int j=0;j<60;j++)   if(mpy[j].count(pll(x, y%(1ll<<j))))    res+=mpy[j][pll(x, y%(1ll<<j))];
        for(int j=0;j<60;j++)   for(int k=0;k<60;k++)   if(mpxy[j][k].count(pll(x%(1ll<<j), y%(1ll<<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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 134 ms 1112 KB Output is correct
3 Correct 133 ms 1036 KB Output is correct
4 Correct 154 ms 1160 KB Output is correct
5 Correct 150 ms 1120 KB Output is correct
6 Correct 105 ms 1088 KB Output is correct
7 Correct 104 ms 1192 KB Output is correct
8 Correct 107 ms 1100 KB Output is correct
9 Correct 110 ms 1112 KB Output is correct
10 Correct 108 ms 1024 KB Output is correct
11 Correct 109 ms 1040 KB Output is correct

Subtask #2
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 4065 ms 54180 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Execution timed out 4070 ms 30188 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #4
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 468 KB Output is correct
2 Correct 134 ms 1112 KB Output is correct
3 Correct 133 ms 1036 KB Output is correct
4 Correct 154 ms 1160 KB Output is correct
5 Correct 150 ms 1120 KB Output is correct
6 Correct 105 ms 1088 KB Output is correct
7 Correct 104 ms 1192 KB Output is correct
8 Correct 107 ms 1100 KB Output is correct
9 Correct 110 ms 1112 KB Output is correct
10 Correct 108 ms 1024 KB Output is correct
11 Correct 109 ms 1040 KB Output is correct
12 Execution timed out 4065 ms 54180 KB Time limit exceeded
13 Halted 0 ms 0 KB -