Submission #1235416

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235416		erering	Arranging Shoes (IOI19_shoes)	C++20	10 / 100	0 ms	328 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);
}
/*
  2
  1 -2 -1 2
 */
long long count_swaps(std::vector<int> s) {
    const int N=s.size();
    while(offset<N)offset*=2;
    queue<int> qr[N],ql[N];
    for(int i=0;i<N;i++){
        if(s[i]>0)qr[s[i]].push(i);
        else ql[abs(s[i])].push(i);
        update(i,1);
    }
    long long ans=0;
    for(int i=0;i<N;i++){
        if(s[i]<0){
            int idx=qr[abs(s[i])].front();
            ans+=query(1,0,i-1,0,offset-1);
            update(i,0);
            ans+=query(1,0,idx-1,0,offset-1);
            update(idx,0);
        }
        else{
            int idx=ql[abs(s[i])].front();
            ans+=query(1,0,i-1,0,offset-1);
            ans+=query(1,0,idx-1,0,offset-1);
            update(i,0);
            update(idx,0);
        }
        qr[abs(s[i])].pop();
        ql[abs(s[i])].pop();
    }
    return ans;
}

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