Submission #297595

#	Time	Username	Problem	Language	Result	Execution time	Memory
297595		shayan_p	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	438 ms	26184 KiB

shoes

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

#define F first
#define S second
#define PB push_back
#define sz(s) (int(s.size()))
#define bit(n, k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int, int> pii;

const int maxn = 2e5 + 10;

map<int, vector<int> > mp;
bool mark[maxn];

int fn[maxn];

void add(int pos, int x){
    for(pos+= 3; pos < maxn; pos+= pos & -pos)
	fn[pos]+= x;
}
int ask(int pos){
    int ans = 0;
    for(pos+= 3; pos > 0; pos-= pos & -pos)
	ans+= fn[pos];
    return ans;
}

ll count_swaps(vector<int> a){
    for(int i = sz(a)-1; i >= 0; i--){
	mp[a[i]].PB(i);
    }
    for(int i = 0; i < sz(a); i++){
	add(i, 1);
    }
    ll ans = 0;
    for(int i = 0; i < sz(a); i++){
	if(mark[i])
	    continue;
	mp[a[i]].pop_back();
	int pos = mp[-a[i]].back();
	mp[-a[i]].pop_back();
	ans+= a[i] > 0;

	ans+= ask(pos) - ask(i) - 1;
	mark[i] = 1;
	mark[pos] = 1;
	add(i, -1);
	add(pos, -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