Submission #1290673

#	Time	Username	Problem	Language	Result	Execution time	Memory
1290673		enzy	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	232 ms	274432 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int maxn=2e5+10;
queue<int>abre[maxn], fecha[maxn];
ll bit[maxn];
int v[maxn];
void update(int x, int q){
	for(int i=x;i<maxn;i+=(i&-i)) bit[i]+=q;
}
int sum(int x){
	int ret=0;
	for(int i=x;i>0;i-=(i&-i)) ret+=bit[i];
	return ret;
}
int query(int l, int r){
	if(l>r) return 0;
	return sum(r)-sum(l-1);
}
ll count_swaps(vector<int> s){
	int n=s.size();
	for(int i=0;i<n;i++){
		update(i+1,1);
		int at=abs(s[i]);
		if(s[i]<0) abre[at].push(i+1);
		else fecha[at].push(i+1);
		v[i+1]=s[i];
	}
	ll resp=0;
	for(int i=1;i<=n;i++){
		if(!query(i,i)) continue;
		int at=abs(v[i]), aux;
		if(v[i]<0){ // to abrindo, logo trago pra minha direita
			aux=fecha[at].front();
			resp+=query(i+1,aux-1);
		}else{ // to fechando, logo trago pra minha esquerda
			aux=abre[at].front();
			resp+=query(i,aux-1);
		}
		update(i,-1); update(aux,-1);
		abre[at].pop(); fecha[at].pop();
	}
	return resp;
}

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