Submission #291627

#	Time	Username	Problem	Language	Result	Execution time	Memory
291627		juggernaut	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	332 ms	142840 KiB

shoes

#include<bits/stdc++.h>
#include"shoes.h"
using namespace std;
int tree[800005],flag[800005];
bool vis[200005];
queue<int>pos[2][100005];
void push(int v,int l,int r){
    if(l!=r){
        flag[v<<1]+=flag[v];
        flag[(v<<1)+1]+=flag[v];
    }
    tree[v]+=flag[v]*(r-l+1);
    flag[v]=0;
}
int get(int v,int l,int r,int ql,int qr){
    if(r<ql||qr<l)return 0;
    push(v,l,r);
    if(ql<=l&&r<=qr)return tree[v];
    int mid=(l+r)>>1;
    return get(v<<1,l,mid,ql,qr)+get((v<<1)+1,mid+1,r,ql,qr);
}
void update(int v,int l,int r,int ql,int qr,int val){
    if(r<ql||qr<l)return;
    push(v,l,r);
    if(ql<=l&&r<=qr){
        flag[v]+=val;
        push(v,l,r);
        return;
    }
    int mid=(l+r)>>1;
    update(v<<1,l,mid,ql,qr,val);
    update((v<<1)+1,mid+1,r,ql,qr,val);
    tree[v]=tree[v<<1]+tree[(v<<1)+1];
}
long long count_swaps(vector<int>v){
    long long cnt=0;
    int q=0,i=0,n=v.size();
    for(;i<n;i++)pos[v[i]>0][abs(v[i])].push(i);
    for(i=0;i<n;i++){
        if(vis[i])continue;
        q=pos[v[i]<0][abs(v[i])].front();
        pos[v[i]<0][abs(v[i])].pop();
        pos[v[i]>0][abs(v[i])].pop();
        vis[q]=1;
        cnt+=abs(get(1,1,n,i+1,i+1)+i-(get(1,1,n,q+1,q+1)+q));
        if(v[i]<0)cnt--;
        update(1,1,n,i+1,q+1,1);
    }
    return cnt;
}
//#include"grader.cpp"

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