Submission #409025

#	Time	Username	Problem	Language	Result	Execution time	Memory
409025		Gurban	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	345 ms	276068 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define ss second
#define ff first
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
typedef long double ld;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
const ll inf = 1e18;
const int mod = 1e9+7; //998244353;
const int maxn = 2e5+5;
const int Xg[4] = {1,0,-1,0}, Yg[4] = {0,1,0,-1};
ll modpw(ll a,ll e) {if(e==0)return 1ll;ll x=modpw(a*a%mod,e>>1);return e&1?x*a%mod:x;}

int T[4*maxn];
int go[maxn];
queue<int> cep[maxn],sag[maxn];

void build(int l,int r,int nd){
	if(l==r){T[nd]=1;return;}
	build(l,(l+r)/2,nd*2);
	build((l+r)/2+1,r,nd*2+1);
	T[nd]=T[nd*2]+T[nd*2+1];
}

int tap(int a,int b,int l,int r,int nd){
	if(r < a or l > b) return 0;
	if(l >= a and r <= b) return T[nd];
	return tap(a,b,l,(l+r)/2,nd*2)+tap(a,b,(l+r)/2+1,r,nd*2+1);
}

void upd(int pos,int l,int r,int nd){
	if(l == r){T[nd]=0;return;}
	if(pos <= (l+r)/2) upd(pos,l,(l+r)/2,nd*2);
	else upd(pos,(l+r)/2+1,r,nd*2+1);
	T[nd]=T[nd*2]+T[nd*2+1];
}

ll count_swaps(vector<int> S){
	for(int i = 0;i < sz(S);i++){
		if(S[i] < 0) cep[-S[i]].push(i);
		else sag[S[i]].push(i);
	}
	int n = sz(S);
	build(0,n-1,1);
	ll ans = 0;
	for(int i = 0;i < n;i++){

		if(go[i]) continue;

		// cout<<i<<' ';
		if(S[i] < 0){
			int pos = sag[-S[i]].front();
			sag[-S[i]].pop(); cep[-S[i]].pop();
			ans += tap(i+1,pos-1,0,n-1,1);
			upd(pos,0,n-1,1);
			go[pos]=1;
			// cout<<pos<<'\n';
		} 
		else {
			int pos = cep[S[i]].front();
			cep[S[i]].pop(); sag[S[i]].pop();
			ans += tap(i+1,pos-1,0,n-1,1)+1;
			upd(pos,0,n-1,1);
			go[pos]=1;
			// cout<<pos<<'\n';
		}
	}
	return ans;
}

#ifdef LOCAL
int main(){
	// clock_t TSTART = clock();
	
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	ios::sync_with_stdio(false);
	cin.tie(nullptr);

	int n;
	cin >> n;
	n *= 2;
	vi v(n);
	for(int i = 0;i < n;i++) cin >> v[i];
	cout<<count_swaps(v);

	// cout << "\nTime elapsed: " << double(clock()-TSTART) / CLOCKS_PER_SEC << " s.\n";
}
#endif

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