제출 #409025

#제출 시각아이디문제언어결과실행 시간메모리
409025GurbanArranging Shoes (IOI19_shoes)C++17
100 / 100
345 ms276068 KiB
#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
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...