Submission #1214173

#	Time	Username	Problem	Language	Result	Execution time	Memory
1214173		Bui_Quoc_Cuong	Arranging Shoes (IOI19_shoes)	C++20	100 / 100	109 ms	29096 KiB

shoes

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 5;

int n;
int a[MAXN];
int b[MAXN];
int st[4 * MAXN], lazy[4 * MAXN];
vector <int> Neg[MAXN], Pos[MAXN];
int L_Neg[MAXN], R_Pos[MAXN], mark[MAXN];

void down(int id, int l, int r){
	if(lazy[id] == 0) return;

	int mid = (l + r) >> 1;

	st[id << 1]+= (mid - l + 1) * lazy[id];
	st[id << 1 | 1]+= (r - mid) * lazy[id];

	lazy[id << 1]+= lazy[id];
	lazy[id << 1 | 1]+= lazy[id];

	lazy[id] = 0;
}

void update(int id, int l, int r, int u, int v, int val){
	if(l > v || r < u) return;
	if(l >= u && r <= v){
		st[id]+= (r - l + 1) * val;
		lazy[id]+= val;
		return;
	}
	int mid = (l + r) >> 1;
	down(id, l, r);
	update(id << 1, l, mid, u, v, val);
	update(id << 1 | 1, mid + 1, r, u, v, val);
	st[id] = st[id << 1] + st[id << 1 | 1];
}

int get(int id, int l, int r, int u, int v){
	if(l > v || r < u) return 0;
	if(l >= u && r <= v) return st[id];
	down(id, l, r);
	int mid = (l + r) >> 1;
	return get(id << 1, l, mid, u, v) + get(id << 1 | 1, mid + 1, r, u, v);
}

long long count_swaps(std::vector <int> S){
	for(int &x : S){
		a[++ n] = x;
	}	
	n /= 2;

	for(int i = 1; i <= 2 * n; i++){
   		if(a[i] < 0) Neg[- a[i]].push_back(i);
   		else Pos[a[i]].push_back(i);
    }
    int cur = 0;

    for(int i = 1; i <= 2 * n; i++) if(!mark[i]){
    	int val = abs(a[i]);

    	int x = Neg[val][L_Neg[val]++];
    	int y = Pos[val][R_Pos[val]++];
    	
    	mark[x] = mark[y] = 1;

    	b[x] = ++ cur;
    	b[y] = ++ cur;
    }

    long long ans = 0;

	for(int i = 1; i <= 2 * n; i++){
		ans+= get(1, 1, 2 * n, b[i], 2 * n);
		update(1, 1, 2 * n, b[i], b[i], 1);
	}

	return ans;
}

// signed main(){
//     ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
//     #define nko "kieuoanh"
//     if(fopen(nko".inp", "r")){
//         freopen(nko".inp", "r", stdin); freopen(nko".out", "w", stdout);
//     }
//     cin >> n;
//     for(int i = 1; i <= 2 * n; i++){
//     	cin >> a[i];
//    		if(a[i] < 0) Neg[- a[i]].push_back(i);
//    		else Pos[a[i]].push_back(i);
//     }
//     int cur = 0;

//     for(int i = 1; i <= 2 * n; i++) if(!mark[i]){
//     	int val = abs(a[i]);

//     	int x = Neg[val][L_Neg[val]++];
//     	int y = Pos[val][R_Pos[val]++];
    	
//     	mark[x] = mark[y] = 1;

//     	b[x] = ++ cur;
//     	b[y] = ++ cur;
//     }

//     long long ans = 0;

// 	for(int i = 1; i <= 2 * n; i++){
// 		ans+= get(1, 1, 2 * n, b[i], 2 * n);
// 		update(1, 1, 2 * n, b[i], b[i], 1);
// 	}
// 	cout << ans;

//     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