oj.uz

Submission #633674

# Submission time Handle Problem Language Result Execution time Memory
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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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