Submission #1310414

#	Time	Username	Problem	Language	Result	Execution time	Memory
1310414		DangerNoodle7591	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	109 ms	32212 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
#pragma GCC target ("avx2")
#pragma GCC optimize ("O3")
#pragma GCC optimize ("unroll-loops")
 
#define lalala ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
//#define int long long int
#define N 200005
//#define big 1000000000000000
//#define fark 0.0000001
#define ll long long
//#define endl "\n"
#define pb push_back
#define ins insert
#define p push
#define f first
#define s second

set<int> sag[N];
set<int> sol[N];

int seg[N*4];
void up(int x,int l,int r,int hed){
    if(l>r)return;
    if(l==r){
        seg[x]=1;return;
    }
    int mid=(l+r)/2;
    if(hed<=mid)up(x*2,l,mid,hed);
    else up(x*2+1,mid+1,r,hed);
    seg[x]=seg[x*2]+seg[x*2+1];
}
int qua(int x,int l,int r,int s,int e){
    if(l>r||r<s||e<l)return 0;
    if(s<=l&&r<=e){
        return seg[x];
    }
    int mid=(l+r)/2;
    return qua(x*2,l,mid,s,e)+ qua(x*2+1,mid+1,r,s,e);
}

ll int count_swaps(vector<int> S){
    for(int i=0;i<S.size();i++){
        if(S[i]<0){
            sol[-S[i]].ins(i);
        }
        else sag[S[i]].ins(i);
    }
    ll int cev=0;
    for(int i=0;i<S.size();i++){
        if(qua(1,1,S.size(),i+1,i+1)==1)continue;
        if(S[i]<0){
            int yer=(*sag[-S[i]].upper_bound(i));
            sag[-S[i]].erase(yer);
            int ara=qua(1,1,S.size(),i+1,yer+1);
            //cout<<i<<" a "<<yer<<" "<<ara<<endl;
            cev+=(yer-i-1)-ara;
            up(1,1,S.size(),yer+1);
        }
        else{
            int yer=(*sol[S[i]].upper_bound(i));
            sol[S[i]].erase(yer);
            int ara=qua(1,1,S.size(),i+1,yer+1);
            //cout<<i<<" b "<<yer<<" "<<ara<<endl;
            cev+=(yer-i)-ara;
            up(1,1,S.size(),yer+1);
        }
        //cout<<cev<<endl;
    }
    return cev;
    
}

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