Submission #1021189

#	Time	Username	Problem	Language	Result	Execution time	Memory
1021189		vjudge1	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	272 ms	157524 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define ll long long
#define mid ((l+r)>>1)
#define pii pair<int,int>
#define fi first
#define se second
#define rep(a,b,c) for(int a=b; a<c; a++)
#define pb push_back

using namespace std;

struct segtree{
	segtree *left, *right;
	int l, r, v=0;
	segtree(int x, int y): l(x), r(y){
		if(l==r) return;
		left = new segtree(l,mid);
		right= new segtree(mid+1,r);
	}
	void update(int x, int y){
		if(y<l || r<x) return;
		if(x<=l && r<=y){
			v+=1;
			return;
		}
		left->update(x,y);
		right->update(x,y);
	}
	int query(int x){
		if(x<l || r<x) return 0;
		if(x<=l && r<=x) return v;
		return (v+left->query(x)+right->query(x));
	}
};

ll count_swaps(vector<int> s) {
	ll ans=0;
	int S=s.size(), n=S/2;
	queue<int> pos[n+1][2];
	segtree ST(0,S);
	rep(i,0,S) pos[abs(s[i])][s[i]>0].push(i), ST.update(i,S);
	rep(i,0,S){
		if(s[i]){
			int a,b;
			a=pos[abs(s[i])][s[i]>0].front();
			b=pos[abs(s[i])][s[i]<0].front();
			pos[abs(s[i])][s[i]>0].pop();
			pos[abs(s[i])][s[i]<0].pop();
			if(a>b) swap(a,b);
			ans+=ST.query(b)-ST.query(a);
			if(s[i]<0) ans--;
			s[a]=0;
			s[b]=0;
			ST.update(a,b);
		}
	}
	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