Submission #424741

#	Time	Username	Problem	Language	Result	Execution time	Memory
424741		alishahali1382	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	153 ms	139872 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>
#pragma GCC optimize("O2")
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define debug(x) {cerr<<#x<<"="<<x<<"\n";}
#define debug2(x, y) {cerr<<"{"<<#x<<", "<<#y<<"}={"<<x<<", "<<y<<"}\n";}
#define debugp(p) {cerr<<#p<<"={"<<p.first<<", "<<p.second<<"}\n";}
#define debugv(abcd) {cerr<<#abcd<<": ";for (auto dcba:abcd) cerr<<dcba<<", ";cerr<<"\n";}
#define pb push_back
#define SZ(x) ((int)x.size())
#define all(x) x.begin(), x.end()

const int inf=1000001000; // 1e9
const ll INF=10000000010000000; // 1e16
const int mod=1000000007;
const int MAXN=200010, LOG=19;

ll ans; // :(
int n, m, k;
int A[MAXN], fen[MAXN];
queue<int> vec[MAXN];

inline void add(int pos, int val){
	for (; pos<MAXN; pos+=pos&-pos) fen[pos]+=val;
}
inline int get(int pos){
	int res=0;
	for (; pos; pos-=pos&-pos) res+=fen[pos];
	return res;
}

ll count_swaps(vector<int> S){
	n=SZ(S);
	for (int i=0; i<n; i++){
		int x=S[i], y=1;
		if (x<0) x=-x, y=-1;
		if (vec[x].size() && S[vec[x].front()]*y<0){
			A[i]=A[vec[x].front()]=m++;
			vec[x].pop();
		}
		else vec[x].push(i);
	}
	for (int i=0; i<n; i++) A[i]=2*A[i]+(S[i]>0)+1;
	for (int i=n-1; ~i; i--){
		ans+=get(A[i]);
		add(A[i], +1);
	}
	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