Submission #684279

#	Time	Username	Problem	Language	Result	Execution time	Memory
684279		Juan	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	71 ms	20336 KiB

shoes

// #include<bits/stdc++.h>
// using namespace std;
// #define pii pair<int, int>
// #define ff first
// #define ss second
// const int maxn = 1e5 + 5;

// vector<int> calc[2*maxn];
// int pos[maxn], bit[maxn], v[maxn];

// void upd(int id){
// 	for(; id < maxn; id+=id&-id) bit[id]++;
// }
// void updn(int id){
// 	for(; id < maxn; id+=id&-id) bit[id]--;
// }
// int soma(int id){
// 	int rt = 0;
// 	for(; id>0; id-=id&-id) rt+=bit[id];
// 	return rt;
// }

// int main(){
// 	int n; cin >> n;
// 	for(int i = 1; i <= n; i++){cin >> v[i]; upd(i);}
// 	for(int i = 1; i <= n; i++){
// 		calc[abs(v[i])+maxn*(v[i]>0)].push_back(i);
// 	}

// 	memset(pos, -1, sizeof pos);
// 	for(int i = 1; i <= n; i++){
// 		for(int j = 0; j < calc[i].size(); j++){
// 			int mn = min(calc[i][j], calc[i+maxn][j]);
// 			int mx = max(calc[i][j], calc[i+maxn][j]);
// 			pos[mn] = mx;
// 		}
// 	}

// 	int ans = 0;
// 	for(int i = 1; i <= n; i++){
// 		if(pos[i]!=-1){
// 			ans += soma(pos[i]-1) - soma(i) + (v[i]>0);
// 			updn(pos[i]), upd(i);
// 		}
// 	}

// 	cout << ans << '\n';
// }

#include<bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
#define ff first
#define ss second
const int maxn = 2e5 + 5;

vector<int> calc[2*maxn];
int pos[maxn], bit[maxn];

void upd(int id){
	for(; id < maxn; id+=id&-id) bit[id]++;
}
void updn(int id){
	for(; id < maxn; id+=id&-id) bit[id]--;
}
int soma(int id){
	int rt = 0;
	for(; id>0; id-=id&-id) rt+=bit[id];
	return rt;
}

int64_t count_swaps(vector<int> v){
	int n = v.size();
	for(int i = 1; i <= n; i++) upd(i);
	for(int i = 1; i <= n; i++){
		calc[abs(v[i-1])+maxn*(v[i-1]>0)].push_back(i);
	}

	memset(pos, -1, sizeof pos);
	for(int i = 1; i <= n; i++){
		for(int j = 0; j < calc[i].size(); j++){
			int mn = min(calc[i][j], calc[i+maxn][j]);
			int mx = max(calc[i][j], calc[i+maxn][j]);
			pos[mn] = mx;
		}
	}

	int64_t ans = 0;
	for(int i = 1; i <= n; i++){
		if(pos[i]!=-1){
			ans += soma(pos[i]-1) - soma(i) + (v[i-1]>0);
			updn(pos[i]), upd(i);
		}
	}

	return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'int64_t count_swaps(std::vector<int>)':
shoes.cpp:81:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |   for(int j = 0; j < calc[i].size(); j++){
      |                  ~~^~~~~~~~~~~~~~~~

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