Submission #291611

#	Time	Username	Problem	Language	Result	Execution time	Memory
291611		juggernaut	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	110 ms	135160 KiB

shoes

#include<bits/stdc++.h>
#include"shoes.h"
using namespace std;
int tree[400005],flag[400005];
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];
}*/
int coef[100005];
void update(int v,int l,int r,int ql,int qr,int val){
    for(int i=ql;i<=qr;i++)coef[i]+=val;
}
int get(int v,int l,int r,int ql,int qr){
    return coef[ql];
}
long long count_swaps(vector<int>v){
    long long cnt=0;
    int q=0,i=0,n=v.size();
    for(i=1;i<n;i+=2)pos[v[i]>0][abs(v[i])].push(i);
    for(i=0;i<n;i+=2){
        q=pos[v[i]<0][abs(v[i])].front();
        pos[v[i]<0][abs(v[i])].pop();
        cnt+=abs(i-(get(1,1,n,q+1,q+1)+q));
        if(v[i]<0)cnt--;
        update(1,1,n,i+2,q,1);
    }
    return cnt;
}

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