oj.uz

Submission #61250

# Submission time Handle Problem Language Result Execution time Memory
61250 2018-07-25T13:54:58 Z Diuven 즐거운 사진 수집 (JOI13_collecting) C++11
0 / 100
 2361 ms 51000 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]--;
            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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Incorrect 4 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 400 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 70.0

# Verdict Execution time Memory Grader output
1 Incorrect 2361 ms 51000 KB Output isn't correct
2 Halted 0 ms 0 KB -