Submission #884680

#	Time	Username	Problem	Language	Result	Execution time	Memory
884680		tamir1	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	428 ms	688724 KiB

shoes

#include "shoes.h"
#include <iostream>
#include <queue>
using namespace std;
queue<int> q[1000000];
bool active[1000000];
int aft[1000000],indx[1000000],st[2000000],lazy[2000000];
void build(int node,int l,int r){
	if(l==r){
		st[node]=indx[l];
		return;
	}
	int mid=(r+l)/2;
	build(node*2,l,mid);
	build(node*2+1,mid+1,r);
}
void update(int node,int l,int r,int L,int R){
	if(lazy[node]!=0){
		if(l==r) st[node]+=lazy[node];
		else{
			lazy[node*2]+=lazy[node];
			lazy[node*2+1]+=lazy[node];
		}
		lazy[node]=0;
	}
	if(l>R || r<L) return;
	if(l>=L && r<=R){
		if(l==r) st[node]++;
		else{
			lazy[node*2]++;
			lazy[node*2+1]++;
		}
		return;
	}
	int mid=(r+l)/2;
	update(node*2,l,mid,L,R);
	update(node*2+1,mid+1,r,L,R);
}
int query(int node,int l,int r,int idx){
	if(lazy[node]!=0){
		if(l==r) st[node]+=lazy[node];
		else{
			lazy[node*2]+=lazy[node];
			lazy[node*2+1]+=lazy[node];
		}
		lazy[node]=0;
	}
	if(l==r) return st[node];
	int mid=(r+l)/2;
	if(idx<=mid) return query(node*2,l,mid,idx);
	else return query(node*2+1,mid+1,r,idx);
}
long long count_swaps(vector<int> s) {
	long long result=0;
	int i,n=s.size(),x,y;
	for(i=0;i<n;i++){
		if(q[-1*s[i]+n/2].empty()) q[s[i]+n/2].push(i);
		else{
			x=q[-1*s[i]+n/2].front();
			q[-1*s[i]+n/2].pop();
			aft[x]=i;
		}
		indx[i]=i;
		active[i]=1;
	}
	build(1,0,n-1);
	for(i=0;i<n;i++){
		if(active[i]){
			x=query(1,0,n-1,i);
			y=query(1,0,n-1,aft[i]);
			active[aft[i]]=0;
			result+=(y-x-(s[i]<0));
			if(i+1<=aft[i]-1) update(1,0,n-1,i+1,aft[i]-1);
		}
	}
	return result;
}

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