Submission #1235383

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235383		erering	Arranging Shoes (IOI19_shoes)	C++20	45 / 100	136 ms	138628 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
#include "shoes.h"
const int MAXN=2e5+5;
int seg[MAXN*4],offset=1;
void update(int idx,int val){
    idx+=offset;
    seg[idx]=val;
    idx/=2;
    while(idx>0){
        seg[idx]=seg[idx*2]+seg[idx*2+1];
        idx/=2;
    }
}
int query(int node,int qlo,int qhi,int lo,int hi){
    if(qlo>qhi)return 0;
    if(lo>=qlo && hi<=qhi)return seg[node];
    if(lo>qhi || hi<qlo)return 0;
    int mid=(lo+hi)/2;
    return query(node*2,qlo,qhi,lo,mid)+query(node*2+1,qlo,qhi,mid+1,hi);
}
long long count_swaps(std::vector<int> s) {
    const int N=s.size();
    while(offset<N)offset*=2;
    queue<int> q[N];
    for(int i=0;i<N;i++){
        if(s[i]>0)q[s[i]].push(i);
        update(i,1);
    }
    long long ans=0;
    for(int i=0;i<N;i++){
        if(s[i]<0){
            int idx=q[abs(s[i])].front();
            q[abs(s[i])].pop();
            ans+=query(1,0,i-1,0,offset-1);
            update(i,0);
         //   cout<<ans<<' ';
            ans+=query(1,0,idx-1,0,offset-1);
            update(idx,0);
          //  cout<<ans<<endl;
        }
    }
    return ans;
}

• Subtask 1: 10 / 10
• Subtask 2: 0 / 20
• Subtask 3: 20 / 20
• Subtask 4: 15 / 15
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15