Submission #293060

#	Time	Username	Problem	Language	Result	Execution time	Memory
293060		charterla	Arranging Shoes (IOI19_shoes)	C++14	25 / 100	253 ms	140280 KiB

shoes

#include "shoes.h"
#include <iostream>
#include <cstdio>
#include <queue>
using namespace std;

int n;
queue<int> shoes[100005][2];
int stn=1,tree[600005];

inline void push_down(int now){
	tree[now<<1]+=tree[now];
	tree[now<<1|1]+=tree[now];
	tree[now]=0;
	return;
}

inline void update(int now,int ls,int rs,int lq,int rq,int value){
	if(rq<ls || rs<lq)return;
	if(lq<=ls && rs<=rq){tree[now]+=value;return;}
	push_down(now);
	
	int mid=(ls+rs)>>1;
	update(now<<1,ls,mid,lq,rq,value);
	update(now<<1|1,mid+1,rs,lq,rq,value);
	return;
}

inline int search(int now,int ls,int rs,int to){
	//cout<<now<<" "<<ls<<" "<<rs<<" "<<to<<endl; 
	if(ls==to && rs==to)return tree[now];
	push_down(now);
	
	int mid=(ls+rs)>>1;
	if(to<=mid)return search(now<<1,ls,mid,to);
	else return search(now<<1|1,mid+1,rs,to);
}

inline int value(int now){return now<0?now*-1:now;}

inline int answer(int a,int b,bool way){
	int ta=a+search(1,1,stn,a+1),tb=b+search(1,1,stn,b+1);//cout<<ta<<" "<<tb<<endl;
	if(way)return tb-ta;else return tb-ta-1;
}

long long count_swaps(vector<int> s) {
	n=s.size();while(stn<n)stn<<=1;
	for(int i=0;i<n;i++)shoes[value(s[i])][s[i]<0].push(i);
	
	long long int ans=0,a=0,b;
	for(int i=0;i<(n>>1);i++){
		b=shoes[value(s[a])][s[a]>=0].front();//cout<<a<<" "<<b<<endl;
		shoes[value(s[a])][0].pop();
		shoes[value(s[a])][1].pop();
		ans+=answer(a,b,s[a]>0);//cout<<ans<<endl;
		
		update(1,1,stn,a+1,b+1,1);
		if(a+1==b)a+=2;else a+=1;
	}
	return ans;
}

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