Submission #289725

#	Time	Username	Problem	Language	Result	Execution time	Memory
289725		AngelKnows	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	322 ms	275704 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std;
#define FOR(i,n) for (int i=1;i<=n;i++)
#define REP(i,a,b) for (int i=a;i<=b;i++)
 
#define pb push_back
#define fi first
#define se second
#define pi pair<int,int>
#define mp make_pair
 
typedef long long ll;

const int inf=0x3f3f3f3f;
const ll linf=1e18;
const int N=200000+1;
const double eps=1e-5;
const int mo=1e9+7;
int n;
int s[N];
ll c[N];
ll ans;
queue<int> l[N],r[N];
int lowbit(int x) {
	return x & -x;
}
void add(int x,int v) {
	while (x<=2*n) {
		c[x]+=v;
		x+=lowbit(x);
	}
}
ll sum(int x) {
	ll res=0;
	while (x>=1) {
		res+=c[x];
		x-=lowbit(x);
	}
	return res;
}
long long count_swaps(std::vector<int> s2) {
	n=int(s2.size());
	n/=2;
    FOR(i,2*n) {
    	s[i]=s2[i-1];
    	if (s[i]>0) r[s[i]].push(i);
    	else l[-s[i]].push(i);
	}
	FOR(i,2*n) add(i,1);
 	FOR(i,2*n) if (sum(i)-sum(i-1)) {
    	if (s[i]<0) {
    		ans+=sum(r[-s[i]].front())-sum(i)-1;
    		add(r[-s[i]].front(),-1);
    		l[-s[i]].pop();
    		r[-s[i]].pop();
		} else {
			ans+=sum(l[s[i]].front())-sum(i);
			add(l[s[i]].front(),-1);
    		l[s[i]].pop();
    		r[s[i]].pop();
		}
	}
	return ans;
}

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