Submission #1217738

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217738		Ak_16	Chorus (JOI23_chorus)	C++20	0 / 100	0 ms	320 KiB

chorus

#include <bits/stdc++.h>
using namespace std;
#define int long long
int n,q;
string s1, s2;

int a[200005];
int b[200005];

int p1[200005];
int p2[200005];

int segp[400005];
int segs[400005];

int fpsum[50];

int brrp[55];
int brrs[55];

int lis[15];

void buildp(){
   for(int i=n-1; i>=1; i--){
    segp[i] = segp[2*i] + segp[2*i+1];
   }
   return;
}

void builds(){
   for(int i=n-1; i>=1; i--){
    segs[i] = segs[2*i] + segs[2*i+1];
   }
   return;
}

void updp(int pos, int val){
    pos += n-1;
    segp[pos] = val;
    for(int i=pos/2; i>=1; i/=2){
        segp[i] = segp[2*i] + segp[2*i+1];
    }
}

void upds(int pos, int val){
    pos += n-1;
    segs[pos] = val;
    for(int i=pos/2; i>=1; i/=2){
        segs[i] = segs[2*i] + segs[2*i+1];
    }
}

int qrp(int l, int r){
    l+=n-1;
    r+=n-1;
    int sm = 0;

    while(l<=r){
        if(l%2==1){
            sm += segp[l];
            l++;
        }
        if(r%2==0){
            sm += segp[r];
            r--;
        }
        l/=2;
        r/=2;
    }
    return sm;
}

int qrs(int l, int r){
    l+=n-1;
    r+=n-1;
    int sm = 0;

    while(l<=r){
        if(l%2==1){
            sm += segs[l];
            l++;
        }
        if(r%2==0){
            sm += segs[r];
            r--;
        }
        l/=2;
        r/=2;
    }
    return sm;
}



signed main(){
    int t;
    int cn1;
    int cn2;
    int mn;

    cin>>t;
    while(t--){
        cin>>n;
        for(int i=0; i<=14; i++){
            lis[i] = 0;
        }


        cin>>q;
        cin>>s1>>s2;
        mn = 1e15;
        cn1 = 0;
        cn2 = 0;
        for(int i=1; i<=n; i++){
            if(s1[i-1]=='1'){
                cn1++;
                a[cn1] = i;
            }
        }

        for(int i=1; i<=n; i++){
            if(s2[n-i]=='1'){
                cn2++;
                b[cn2] = i;
            }
        }

        

        p1[0] = 0;
        p2[0] = 0;

        for(int i=1; i<=cn1; i++){
            p1[i] = p1[i-1] + a[i];
        }

        for(int i=1; i<=cn2; i++){
            p2[i] = p2[i-1] + b[i];
        }

        if(cn1+cn2<=n){
            cout<<-1<<endl;
        }

        else {
            for(int i=n+1-cn2; i<=cn1; i++){
                mn = min(mn, p1[i] + p2[n+1-i] - (i)*(i+1)/2 - (n+1-i)*(n+2-i)/2);
            }
            cout<<mn<<endl;
        }

        for(int i=0; i<n; i++){
            if(s1[i]=='0'){
                segp[n+i] = 0;
                segs[n+i] = 0;
            }
            else {
                segp[n+i] = 1;
                segs[n+i] = i+1;
            }
        }

        int cur = 0;
        for(int i=1; i<=n; i++){
            if(s2[n-i]=='1'){
                cur++;
                lis[cur] = i;
            }
        }

        buildp();
        builds();

        while(q--){
          int n1, n2;
          cin>>n1>>n2;
          mn = 1e15;

          if(n1==2){

             if(s2[n2-1]=='0'){
                s2[n2-1]='1';
                cn2++;
                int com = 0;
                for(int i=1; i<cn2; i++){
                    if(lis[i]<n+1-n2){
                        com++;
                    }
                }

                for(int i=cn2+1; i>=com+2; i--){
                    lis[i] = lis[i-1];
                }

                lis[com+1] = n+1-n2;
            }

             else {
                s2[n2-1] = '0';
                cn2--;
                int com = 0;

                for(int i=1; i<=cn2+1; i++){
                    if(lis[i] == n+1-n2){
                        com = i;
                    }
                }

                for(int i=com; i<=cn2; i++){
                    lis[i] = lis[i+1];
                }

                lis[cn2+1] = 0;
            }

            }

             else {
                if(s1[n2-1]=='0'){
                    s1[n2-1]='1';
                    updp(n2, 1);
                    upds(n2, n2);
                    cn1++;
                }
                else {
                    s1[n2-1] = '0';
                    updp(n2, 0);
                    upds(n2, 0);
                    cn1--;
                }
            }

            if(cn1+cn2<=n){cout<<-1<<endl;}

            

            else {

                for(int i=1; i<=20; i++){
                brrs[i] = 1e15;
              }

            int suu[25];

            suu[1] = qrs(1, n);
            for(int i=2; i<=cn2; i++){
                suu[i] = suu[i-1] - segs[2*n+2-i];
            }
              brrp[1] = qrp(1,n);
              for(int i=2; i<=cn2; i++){
                brrp[i] = brrp[i-1] - segp[2*n+1-i];
              }
            

              for(int i=1; i<=cn2; i++){
                brrs[n+1-brrp[i]] = suu[i];
              }
            fpsum[0] = 0;

            for(int i=1; i<=cn2; i++){
                fpsum[i] = fpsum[i-1] + lis[i];
            }
             
             for(int i=n+1-cn1; i<=cn2; i++){
                mn = min(mn, fpsum[i] + brrs[i] - i*(i+1)/2 - (n+1-i)*(n+2-i)/2);
             }


             


            
             
          
          
          cout<<mn<<endl;
            }
        }

    }
    
   return 0;
}

• Subtask 1: 0 / 16
• Subtask 2: 0 / 24
• Subtask 3: 0 / 21
• Subtask 4: 0 / 26
• Subtask 5: 0 / 13