Submission #650014

#	Time	Username	Problem	Language	Result	Execution time	Memory
650014		Markomafko972	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	82 ms	16028 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
#define X first
#define Y second
#define pb push_back
#define pii pair<int, int>
typedef long long ll;
using namespace std;

const int MOD = 1e9 + 7;
const ll INF = 1e18;
const int OFF = (1 << 20);

int n, koji = 1;
int bio[200005];
int loga[200005];
pair<int, int> gdje[100005];
int reshi[100005];

vector<int> br[100005];
vector<int> mbr[100005];

void update(int x, int y) {
	x++;
	for (x; x <= n; x += x & -x) loga[x] += y;
}

int query(int x) {
	int out = 0;
	x++;
	for (x; x > 0; x -= x & -x) out += loga[x];
	return out;
}

long long count_swaps(vector<int> v) {
	n = v.size();
	
	for (int i = 0; i < n; i++) {
		if (v[i] < 0) mbr[-v[i]].push_back(i);
		else br[v[i]].push_back(i);
	}
	
	for (int i = 1; i <= n/2; i++) {
		while (br[i].size() > 0) {
			gdje[koji].X = min(mbr[i].back(), br[i].back());
			gdje[koji].Y = max(mbr[i].back(), br[i].back());
			v[mbr[i].back()] = -koji;
			v[br[i].back()] = koji;
			koji++;
			br[i].pop_back();
			mbr[i].pop_back();
		}
	}
	
	/*for (int i = 0; i < n; i++) {
		if (bio[abs(v[i])] == 0) {
			bio[abs(v[i])] = koji;
			v[i] = v[i]/abs(v[i])*koji;
			gdje[koji].X = i;
			koji++;
		}
		else {
			gdje[bio[abs(v[i])]].Y = i;
			v[i] = v[i]/abs(v[i])*bio[abs(v[i])];
		}
	}*/
	
	for (int i = 0; i < n; i++) update(i, 1);
	
	ll sol = 0;
	for (int i = 0; i < n; i++) {
		if (reshi[abs(v[i])]) continue;
		int tren = query(gdje[abs(v[i])].Y) - query(gdje[abs(v[i])].X);
		if (v[i] < 0) tren--;
		sol += tren;
		
		update(gdje[abs(v[i])].X+1, 1);
		update(gdje[abs(v[i])].Y, -1);
		reshi[abs(v[i])] = 1;
	}
	return sol;
}

Compilation message (stderr)

shoes.cpp: In function 'void update(int, int)':
shoes.cpp:25:7: warning: statement has no effect [-Wunused-value]
   25 |  for (x; x <= n; x += x & -x) loga[x] += y;
      |       ^
shoes.cpp: In function 'int query(int)':
shoes.cpp:31:7: warning: statement has no effect [-Wunused-value]
   31 |  for (x; x > 0; x -= x & -x) out += loga[x];
      |       ^

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