oj.uz

답안 #633674

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
633674 2022-08-23T03:28:56 Z Fake4Fun 즐거운 사진 수집 (JOI13_collecting) C++14
100 / 100
 897 ms 61840 KB 
#include<iostream>
#define FBIT(x) ((1<<x)-1)
using namespace std;
const int N=1<<20;
int n,q;
int al[2][22],IT[2][N<<1];
void update(int id,int p){
    short dif=(!IT[id][p]?1:-1), layer=0;
    IT[id][p]^=1;
    while(p!=1){
        p>>=1, ++layer;
        bool o=!(IT[id][p]&FBIT(layer));
        al[id][layer]-=o;
        IT[id][p]+=dif;
        o=!(IT[id][p]&FBIT(layer));
        al[id][layer]+=o;
    }
}
int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++) al[0][i]=al[1][i]=1<<(n-i);
    int id,x;
    long long ans;
    while(q--){
        cin>>id>>x;
        update(id,(1<<n)+x-1);
        ans=0;
        for(int i=n;i>=0;i--)
            ans+=(1ll<<(2*(n-i)))-(4ll*al[0][i+1]*al[1][i+1]);
        cout<<ans<<'\n';
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct

Subtask #2
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 336 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct

Subtask #3
70.0 / 70.0

# 결과 실행 시간 메모리 Grader output
1 Correct 856 ms 61552 KB Output is correct
2 Correct 816 ms 61572 KB Output is correct
3 Correct 789 ms 50540 KB Output is correct
4 Correct 837 ms 61840 KB Output is correct
5 Correct 850 ms 61336 KB Output is correct
6 Correct 763 ms 60176 KB Output is correct
7 Correct 897 ms 61540 KB Output is correct
8 Correct 825 ms 61672 KB Output is correct
9 Correct 703 ms 49188 KB Output is correct
10 Correct 735 ms 51668 KB Output is correct
11 Correct 828 ms 60300 KB Output is correct
12 Correct 827 ms 60200 KB Output is correct
13 Correct 700 ms 51628 KB Output is correct