Submission #259748

#	Time	Username	Problem	Language	Result	Execution time	Memory
259748		youssefbou62	Arranging Shoes (IOI19_shoes)	C++14	10 / 100	17 ms	19456 KiB

shoes

	#include <bits/stdc++.h>
	#include "shoes.h"
	#define ll long long 
	#define pb push_back
	#define sz(x) (int)x.size()
	#define all(x) x.begin(),x.end()
	#define pi pair<int,int> 
	#define fi first
	#define se second 	
	using namespace std; 

	const int MAXN = 2e5+5 ; 
	vector<int> posR[MAXN],posL[MAXN] ; 
	int ft[MAXN] , n ; 

	int lsO(int x){
		return x&(-x); 
	}
	int sum(int x ){
		if( x<=0 )return 0 ;
		int s = 0; 
		for(int i = x; i > 0 ; i -= lsO(i) )
			s += ft[i]; 
		return s ; 
	}
	int pref(int x){
		return sum(2*n+1)-sum(x-1); 
	}
	void update (int x ){
		if(x <= 0 )return ; 
		for(int i = x ; i <= 2*n+1  ; i+= lsO(i))
			ft[i]++; 
	}
	long long count_swaps(std::vector<int> s) {
		ll ans = 0;
		n = sz(s)/2 ; 
		for(int i=0;i<sz(s);i++ ){
			int a = s[i] ; 
			if( a > 0 )posR[a].pb(i+1);
			else posL[-a].pb(i+1) ;
		}	
		priority_queue<pi,vector<pi>,greater<pi>> q;
		
		for(int i = 1 ; i <= n ; i++ ){
			if( posR[i].empty() )continue ; 
			reverse(all(posR[i]));
			reverse(all(posL[i])); 
			q.push({posR[i].back() + posL[i].back(),i}); 
		}
		int toadd = 0; 
 
		for(int i = 1 ; i <= n ; i++ ){
			int l = i * 2 - 1 , r = i*2  ; 
			int j = q.top().se ; 
			int x = posL[j].back() , y = posR[j].back(); 
			x += pref(x-1) ;
			update (x-1);  
			y += pref(y);

			update(y-1);  
			toadd = x + y - l - r ; 
			posR[j].pop_back(); 
			posL[j].pop_back(); 
			q.pop(); 
			// cout << x << " " << y << " "  << j << " " << toadd<< endl;
			// if( !posL[j].empty() )
			// q.push({posR[j].back() + posL[j].back(),j}); 
			while ( !q.empty())q.pop() ;
			for(int j = 1 ; j <= n ; j++ ){
				if( posR[j].empty() )continue ; 
				for(int &x : posL[j])x+=pref(x); 
				for(int &x : posR[j])x+=pref(x); 
				sort(all(posR[j]));
				sort(all(posL[j])); 
			
				reverse(all(posR[j]));
				reverse(all(posL[j])); 
			
				q.push({posL[i].back()+posR[i].back(),j}); 
			}
			ans += 1LL*toadd ;


		}
		return ans;
	}

	// int main() {
	// 	int n;
	// 	assert(1 == scanf("%d", &n));
	// 	vector<int> S(2 * n);
	// 	for (int i = 0; i < 2 * n; i++)
	// 		assert(1 == scanf("%d", &S[i]));
	// 	fclose(stdin);

	// 	long long result = count_swaps(S);

	// 	printf("%lld\n", result);
	// 	fclose(stdout);
	// 	return 0;
	// }

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