제출 #1273068

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1273068		nthvn	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	32 ms	10152 KiB

shoes

#include "bits/stdc++.h"
using namespace std;

#define fi first
#define se second
#define pii pair<int,int> 
#define all(x) x.begin(), x.end()
#define sz(x) (int)x.size()
#define pb push_back
#define ll long long
const int N = 4e5+5;


int n, a[N], b[N];
vector<int> pos[N];
vector<pii> v;
int last[N];
ll ans;

struct BIT{
	int bit[N];
	void update(int i, int x){
		for(;i<=n;i+=i&-i) bit[i]+=x;
	}
	int get(int i){
		int ans =0;
		for(;i;i-=i&-i) ans+= bit[i];
		return ans;
	}
}bit;



void preprocess(){
	for(int i=n;i>=1;i--){
		if(a[i]<0) pos[-a[i]].pb(i);
	}
	int cnt=0;
	for(int i=1;i<=n;i++){
		if(a[i]>0){
			int p = pos[a[i]].back();
			// cerr<<i<<" "<<p<<"; ";
			pos[a[i]].pop_back();
			b[i]= b[p] = ++cnt;
			if(p>i) {
				ans++;
			}
			
		}
	}
}

ll count_swaps(vector<int> S){
	n= sz(S);
	for(int i=1;i<=n;i++) a[i]= S[i-1];
	preprocess();
	
	for(int i=1;i<=n;i++){
		if(!last[b[i]]) {
			last[b[i]]=i;
			ans-= bit.get(i);
		}
		else{
			ans+=bit.get(last[b[i]]);
			bit.update(last[b[i]],1);
			ans+= 2*(bit.get(i)-bit.get(last[b[i]]));
		}
	}
	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