Submission #258865

#	Time	Username	Problem	Language	Result	Execution time	Memory
258865		MarWarPL	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	149 ms	18424 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
using namespace std;
#define FOR(i,x,y) for(int i=(int)(x);i<(int)(y);++i)
#define FORE(i,x,y) for(int i=(int)(x);i<=(int)(y);++i)
#define FORD(i,x,y) for(int i=(int)(x);i>=(int)(y);--i)
#define PB push_back
#define ST first
#define ND second
typedef long long ll;
typedef pair<int,int> pii;
const int MAXT=(1<<19)+7;
const int MAXN=2e5+7;

int n;
int t[MAXT];
int lazy[MAXT];
bool vis[MAXN];
vector<int> pos[MAXN];
void Bld(int v,int vl,int vr){
    if(vl==vr){
        t[v]=vl;
    }else{
        int vm=(vl+vr)/2;
        Bld(v*2,vl,vm);
        Bld(v*2+1,vm+1,vr);
    }
}
void Push(int v){
    t[v*2]+=lazy[v];
    lazy[v*2]+=lazy[v];
    t[v*2+1]+=lazy[v];
    lazy[v*2+1]+=lazy[v];
    lazy[v]=0;
}
void Add(int v,int vl,int vr,int l,int r,int val){
    if(l>r)return;
    if(l==vl&&r==vr){
        t[v]+=val;
        lazy[v]+=val;
    }else{
        Push(v);
        int vm=(vl+vr)/2;
        Add(v*2,vl,vm,l,min(vm,r),val);
        Add(v*2+1,vm+1,vr,max(l,vm+1),vr,val);
    }
}
int Qry(int v,int vl,int vr,int vq){
    if(vl==vr){
        return t[v];
    }else{
        int vm=(vl+vr)/2;
        Push(v);
        if(vq<=vm)return Qry(v*2,vl,vm,vq);
        else return Qry(v*2+1,vm+1,vr,vq);
    }
}
long long count_swaps(std::vector<int> s) {
    n=s.size();
    FORD(i,n-1,0){
        if(s[i]>0)pos[s[i]*2].PB(i);
        else pos[s[i]*(-2)-1].PB(i);
    }
    ll ans=0;
    Bld(1,0,n-1);
    FOR(i,0,n){
        int x,y;
        if(s[i]>0)x=s[i]*2,y=x-1;
        else x=s[i]*(-2)-1,y=x+1;
        if(pos[x].empty()||pos[x].back()!=i)continue;
        int xpos=Qry(1,0,n-1,pos[x].back());
        int ypos=Qry(1,0,n-1,pos[y].back());
        if(x&1){
            ans+=ypos-xpos-1;
        }else{
            ans+=ypos-xpos;
        }
        Add(1,0,n-1,pos[y].back(),n-1,-1);
        pos[x].pop_back();
        pos[y].pop_back();
    }
	return ans;
}
/*
2
2 1 -1 -2

3
-2 2 2 -2 -2 2

3
3 -1 2 1 -3 -2

4
3 -1 2 1 -3 -4 -2 4

5
1 2 3 4 5 -5 -4 -3 -2 -1

3
1 2 3 -3 -2 -1

1
-1 1
*/

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