oj.uz

Submission #61253

# Submission time Handle Problem Language Result Execution time Memory
61253 2018-07-25T13:56:32 Z Diuven 즐거운 사진 수집 (JOI13_collecting) C++11
100 / 100
 2625 ms 236164 KB 
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MX=100010, inf=2e9;

int k, n, q;

struct st{
    uint8_t tree[1<<21];
    bool Arr[(1<<20)+1];
    int cnt[22];
    int len[22];
    void init(){
        cnt[k]=1;
        for(int i=k; i>=0; i--) len[i]=len[i+1]+cnt[i]*(1<<i);
    }
    ll upt(int v, int s, int e, int pos, int X[], int d=k){
        if(pos<s || e<pos) return 0LL;
        if(s==e){
            Arr[pos]=!Arr[pos];
            tree[v]=Arr[pos];
            return 0LL;
        }
        ll res=0;
        if(tree[v]!=3){
            res+=X[d]/(1<<d) * 4;
            cnt[d]--; cnt[d-1]+=2;
            tree[v]=3;
        }
        res+=upt(v*2,s,(s+e)/2,pos,X,d-1);
        res+=upt(v*2+1,(s+e)/2+1,e,pos,X,d-1);
        if(tree[v*2]==tree[v*2+1] && tree[v*2]!=3){
            res-=X[d]/(1<<d) * 4;
            cnt[d]++; cnt[d-1]-=2;
            tree[v]=tree[v*2];
        }
        return res;
    }
    ll upt(int pos, int S[]){
        ll ans=upt(1,1,n,pos,S);
        for(int i=k; i>=0; i--) len[i]=len[i+1]+(1<<i)*cnt[i];
        return ans;
    }
} X, Y;

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    cin>>k>>q; n=(1<<k);
    X.init(); Y.init();
    ll ans=1;
    for(int i=1; i<=q; i++){
        int t, x; cin>>t>>x;
        st &A=(t==0 ? X : Y), &B=(t==1 ? X : Y);
        ans+=A.upt(x, B.len);
        cout<<ans<<'\n';
    }
    return 0;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 468 KB Output is correct
3 Correct 3 ms 544 KB Output is correct
4 Correct 2 ms 676 KB Output is correct
5 Correct 2 ms 676 KB Output is correct
6 Correct 3 ms 676 KB Output is correct
7 Correct 3 ms 676 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 676 KB Output is correct
2 Correct 5 ms 676 KB Output is correct
3 Correct 5 ms 676 KB Output is correct
4 Correct 5 ms 820 KB Output is correct
5 Correct 4 ms 820 KB Output is correct
6 Correct 3 ms 920 KB Output is correct
7 Correct 5 ms 920 KB Output is correct
8 Correct 5 ms 920 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 2354 ms 33688 KB Output is correct
2 Correct 2001 ms 51308 KB Output is correct
3 Correct 1938 ms 63100 KB Output is correct
4 Correct 2289 ms 85748 KB Output is correct
5 Correct 2324 ms 102684 KB Output is correct
6 Correct 2297 ms 119224 KB Output is correct
7 Correct 2559 ms 137924 KB Output is correct
8 Correct 2602 ms 155464 KB Output is correct
9 Correct 2195 ms 165696 KB Output is correct
10 Correct 2372 ms 184564 KB Output is correct
11 Correct 2625 ms 205056 KB Output is correct
12 Correct 2345 ms 222092 KB Output is correct
13 Correct 2228 ms 236164 KB Output is correct