Submission #500347

#	Time	Username	Problem	Language	Result	Execution time	Memory
500347		SharpEdged	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	126 ms	11264 KiB

shoes

#include <bits/stdc++.h>
#include <shoes.h>

using namespace std;

#define f first
#define s second
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define LSB(x) ((x) & -(x))

typedef long long ll;
typedef long double ld;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void __print(int x) {cerr << x;}
void __print(long x) {cerr << x;}
void __print(long long x) {cerr << x;}
void __print(unsigned x) {cerr << x;}
void __print(unsigned long x) {cerr << x;}
void __print(unsigned long long x) {cerr << x;}
void __print(float x) {cerr << x;}
void __print(double x) {cerr << x;}
void __print(long double x) {cerr << x;}
void __print(char x) {cerr << '\'' << x << '\'';}
void __print(const char *x) {cerr << '\"' << x << '\"';}
void __print(const string &x) {cerr << '\"' << x << '\"';}
void __print(bool x) {cerr << (x ? "true" : "false");}
 
template<typename T, typename V>
void __print(const pair<T, V> &x) {cerr << '{'; __print(x.first); cerr << ", "; __print(x.second); cerr << '}';}
template<typename T>
void __print(const T &x) {int f = 0; cerr << '{'; for (auto &i: x) cerr << (f++ ? ", " : ""), __print(i); cerr << "}";}
void _print() {cerr << "]\n";}
template <typename T, typename... V>
void _print(T t, V... v) {__print(t); if (sizeof...(v)) cerr << ", "; _print(v...);}
#ifdef DEBUG
#define dbg(x...) cerr << "\e[DEBUG] "<<__func__<<": "<<__LINE__<<", [" << #x << "] = ["; _print(x);
#else
#define dbg(x...)
#endif

const int INF = 1e9 + 5;
const int mxN = 2e5 + 5;

int bit[mxN];

int query(int x){
	if (x == -1) return 0;
	int val = 0;
	for (x++; x > 0; x -= LSB(x)) val += bit[x];
	return val;
}

int query(int l, int r){
	return query(r) - query(l-1);
}

void update(int x, int v){
	for (x++; x < mxN; x += LSB(x)) bit[x] += v;
}

ll count_swaps(vector<int> s){
	int n = s.size();
	int lE = 0, rE = 1;
	vector<int> red(n);
	vector<int> cntL(n+1);
	vector<int> cntR(n+1);
	map<pair<int, int>, int> mp;
	for (int i = 0; i < n; i++){
		int shoe = abs(s[i]);
		if (s[i] < 0){
			cntL[shoe]++;
			pair<int, int> comp = {-s[i], cntL[shoe]};
			if (mp.count(comp)){
				red[i] = mp[comp]-1;
			} else {
				red[i] = lE;
				mp[{s[i], cntL[shoe]}] = lE;
				lE += 2;
				rE += 2;
			}
		} else {
			cntR[shoe]++;
			pair<int, int> comp = {-s[i], cntR[shoe]};
			if (mp.count(comp)){
				red[i] = mp[comp]+1;
			} else {
				red[i] = rE;
				mp[{s[i], cntR[shoe]}] = rE;
				rE += 2;
				lE += 2;
			}
		}
	}
	ll ans = 0;
	for (int i = 0; i < n; i++){
		ans += query(red[i]+1, mxN-2);
		update(red[i], 1);
	}
	return ans;
}

void solve(){
	int n;
	cin >> n;
	vector<int> s(n);
	for (int i = 0; i < n; i++){
		cin >> s[i];
	}
	cout << count_swaps(s) << "\n";
}

/*int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;
	//cin >> t;
	while (t--){
		solve();
	}
	return 0;
}*/

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