Submission #547989

#	Time	Username	Problem	Language	Result	Execution time	Memory
547989		MilosMilutinovic	Bubble Sort 2 (JOI18_bubblesort2)	C++14	100 / 100	4258 ms	78120 KiB

bubblesort2

#include "bubblesort2.h"
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
const int N=500050;
const int M=4*N;
int n,q,a[N],x[N],v[N],was[2*N];
int st[M],val[M],root,ls[M],rs[M],tsz,lzy[M];
void push(int c,int ss,int se){
    if(ss!=se){
        if(!ls[c])ls[c]=++tsz;
        if(!rs[c])rs[c]=++tsz;
        val[ls[c]]+=lzy[c];
        val[rs[c]]+=lzy[c];
        st[ls[c]]+=lzy[c];
        st[rs[c]]+=lzy[c];
        lzy[ls[c]]+=lzy[c];
        lzy[rs[c]]+=lzy[c];
    }
    lzy[c]=0;
}
void Set(int&c,int ss,int se,int qs,int qe,int w){
    if(!c)c=++tsz;
    if(ss>se||ss>qe||se<qs)return;
    if(qs<=ss&&se<=qe){st[c]+=w,lzy[c]+=w,val[c]+=w,push(c,ss,se);return;}
    push(c,ss,se);
    int mid=ss+se>>1;
    Set(ls[c],ss,mid,qs,qe,w);
    Set(rs[c],mid+1,se,qs,qe,w);
    val[c]=-1e9;
    if(ls[c])val[c]=max(val[c],val[ls[c]]);
    if(rs[c])val[c]=max(val[c],val[rs[c]]);
}
void Act(int c,int ss,int se,int qi,int i){
    if(ss==se){val[c]=(i==1?st[c]:-1e9);return;}
    push(c,ss,se);
    int mid=ss+se>>1;
    if(qi<=mid)Act(ls[c],ss,mid,qi,i);
    else Act(rs[c],mid+1,se,qi,i);
    val[c]=max(val[ls[c]],val[rs[c]]);
}
void Input(vector<int> A,vector<int> X,vector<int> V){
    n=A.size(),q=X.size();
    vector<pair<int,int>> cpr;
    for(int i=0;i<n;i++)cpr.pb({A[i],i});
    for(int i=0;i<q;i++)cpr.pb({V[i],X[i]});
    sort(cpr.begin(),cpr.end());
    cpr.erase(unique(cpr.begin(),cpr.end()),cpr.end());
    for(int i=0;i<n;i++)a[i]=(int)(lower_bound(cpr.begin(),cpr.end(),mp(A[i],i))-cpr.begin())+1;
    for(int i=0;i<q;i++)v[i]=(int)(lower_bound(cpr.begin(),cpr.end(),mp(V[i],X[i]))-cpr.begin())+1;
    for(int i=0;i<q;i++)x[i]=X[i];
}
void Print(int c,int ss,int se){
    if(ss==se){if(ss<=10)printf("debug at %d == %d\n",ss,st[c]);return;}
    int mid=ss+se>>1;
    Print(ls[c],ss,mid);
    Print(rs[c],mid+1,se);
}
vector<int> countScans(vector<int> A,vector<int> X,vector<int> V){
    Input(A,X,V);
    //for(int i=0;i<n;i++)printf("%d ",a[i]);puts("");
    for(int i=0;i<n;i++)Set(root,1,2*N,a[i],a[i],i+1),was[a[i]]=1;
    for(int i=0;i<q;i++)if(!was[v[i]])Set(root,1,2*N,v[i],v[i],x[i]+1),Act(root,1,2*N,v[i],0),was[v[i]]=1;
    for(int i=0;i<n;i++)Set(root,1,2*N,a[i],2*N,-1);
    for(int i=0;i<n;i++)Act(root,1,2*N,a[i],1);
    //for(int i=0;i<n;i++)printf("%d ",a[i]);puts("");
    vector<int> ans;
    for(int i=0;i<q;i++){
        Set(root,1,2*N,a[x[i]],2*N,1);
        //Print(root,1,2*N);
        Act(root,1,2*N,a[x[i]],0);
        a[x[i]]=v[i];
        //printf("ww %d\n",v[i]);
        Set(root,1,2*N,a[x[i]],2*N,-1);
        Act(root,1,2*N,a[x[i]],1);
        ans.pb(val[root]);
    }
    return ans;
}

Compilation message (stderr)

bubblesort2.cpp: In function 'void Set(int&, int, int, int, int, int)':
bubblesort2.cpp:28:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   28 |     int mid=ss+se>>1;
      |             ~~^~~
bubblesort2.cpp: In function 'void Act(int, int, int, int, int)':
bubblesort2.cpp:38:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   38 |     int mid=ss+se>>1;
      |             ~~^~~
bubblesort2.cpp: In function 'void Print(int, int, int)':
bubblesort2.cpp:56:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   56 |     int mid=ss+se>>1;
      |             ~~^~~

• Subtask 1: 17 / 17
• Subtask 2: 21 / 21
• Subtask 3: 22 / 22
• Subtask 4: 40 / 40