oj.uz

Submission #1023328

# Submission time Handle Problem Language Result Execution time Memory
1023328 2024-07-14T15:47:22 Z kustizus 즐거운 사진 수집 (JOI13_collecting) C++17
100 / 100
 1405 ms 90708 KB 
// #pragma GCC optimize("O3,unroll-loops")
// #pragma GCC target("avx2,fma,bmi2,popcnt,lzcnt")
#include <bits/stdc++.h>
#define int long long
using namespace std;
mt19937_64 rnd(chrono::high_resolution_clock::now().time_since_epoch().count());
const int N=1048576;
int n,q,now[25],b[N+5];
struct Segment_Tree{
    bool Nam[2*N+5];
    int ST[2*N+5],a[25];
    void Build(){
        Nam[1]=true;
    }
    void Update(int id, int l, int r, int pos){
        if (l>pos || r<pos) return;
        if (l==r){
            ST[id]=r-l+1-ST[id];
            return;
        }
        int md=l+r>>1;
        Update(id<<1,l,md,pos);
        Update(id<<1|1,md+1,r,pos);
        ST[id]=ST[id<<1]+ST[id<<1|1];
    }
    void Check(int id, int l, int r, int pos){
        if ((id==1 && (!ST[id] || ST[id]==r-l+1)) || (id>1 && (!ST[id] || ST[id]==r-l+1) && (ST[id>>1] && ST[id>>1]!=(r-l+1)*2))){
            if (!Nam[id]){
                Nam[id]=true;
                ++a[b[r-l+1]];
            }
        }
        else{
            if (Nam[id]){
                Nam[id]=false;
                --a[b[r-l+1]];
            }
        }
        if (l>pos || r<pos) return;
        if (l==r) return;
        int md=l+r>>1;
        Check(id<<1,l,md,pos);
        Check(id<<1|1,md+1,r,pos);
    }
} h,c;
void Solve(){
    cin>>n>>q;
    h.Build();
    c.Build();
    h.a[n]=c.a[n]=1;
    int mx=1<<n;
    b[1]=0;
    for (int i=2;i<=N;++i)
        b[i]=b[i/2]+1;
    now[0]=1;
    for (int i=1;i<=n;++i) now[i]=now[i-1]*4+1;
    while (q--){
        int t,x;
        cin>>t>>x;
        if (!t){
            h.Update(1,1,mx,x);
            h.Check(1,1,mx,x);
        }
        else{
            c.Update(1,1,mx,x);
            c.Check(1,1,mx,x);
        }
        int ans=now[n],xx=0,yy=0;
        for (int i=n;i>=0;--i){
            xx*=2,yy*=2;
            xx+=h.a[i];
            yy+=c.a[i];
            int d=(xx*c.a[i]+yy*h.a[i])-c.a[i]*h.a[i];
            ans-=d*(now[i]-1);
        }
        cout<<ans<<"\n";
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    // freopen ("FILE.INP","r",stdin);
    // freopen ("FILE.OUT","w",stdout);
    int t=1;
    // cin>>t;
    while (t--) Solve();
    cerr<<"\nTIME: "<<1000*clock()/CLOCKS_PER_SEC<<"ms\n";
}

Compilation message

collecting.cpp: In member function 'void Segment_Tree::Update(long long int, long long int, long long int, long long int)':
collecting.cpp:21:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   21 |         int md=l+r>>1;
      |                ~^~
collecting.cpp: In member function 'void Segment_Tree::Check(long long int, long long int, long long int, long long int)':
collecting.cpp:41:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   41 |         int md=l+r>>1;
      |                ~^~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12376 KB Output is correct
2 Correct 4 ms 12380 KB Output is correct
3 Correct 4 ms 12420 KB Output is correct
4 Correct 4 ms 12380 KB Output is correct
5 Correct 4 ms 12504 KB Output is correct
6 Correct 4 ms 12532 KB Output is correct
7 Correct 4 ms 12536 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 12636 KB Output is correct
2 Correct 4 ms 12636 KB Output is correct
3 Correct 4 ms 12636 KB Output is correct
4 Correct 5 ms 12632 KB Output is correct
5 Correct 6 ms 12636 KB Output is correct
6 Correct 5 ms 12636 KB Output is correct
7 Correct 4 ms 12612 KB Output is correct
8 Correct 4 ms 12636 KB Output is correct

Subtask #3
70.0 / 70.0

# Verdict Execution time Memory Grader output
1 Correct 1317 ms 90452 KB Output is correct
2 Correct 1353 ms 90420 KB Output is correct
3 Correct 1199 ms 72864 KB Output is correct
4 Correct 1315 ms 90708 KB Output is correct
5 Correct 1340 ms 90224 KB Output is correct
6 Correct 1160 ms 89172 KB Output is correct
7 Correct 1339 ms 90376 KB Output is correct
8 Correct 1405 ms 90448 KB Output is correct
9 Correct 1163 ms 71592 KB Output is correct
10 Correct 1153 ms 74064 KB Output is correct
11 Correct 1288 ms 88988 KB Output is correct
12 Correct 1275 ms 89172 KB Output is correct
13 Correct 1127 ms 73888 KB Output is correct