| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 172999 | FieryPhoenix | Arranging Shoes (IOI19_shoes) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cstdio>
#include <map>
#include <queue>
#include <set>
#include <iomanip>
#include <deque>
#include <cassert>
#include <ctime>
#include <cstring>
#include <cstdlib>
#include <chrono>
#include <ctime>
#include <random>
#include <stack>
#include <unordered_set>
#include <unordered_map>
#include <iterator>
#include <climits>
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007
int N;
map<int,int>mp;
int tree[200001];
bool dead[200001];
void update(int pos, int val){
while (pos<=N*2){
tree[pos]+=val;
pos+=(pos&(-pos));
}
}
int query(int pos){
int ans=0;
while (pos>=1){
ans+=tree[pos];
pos-=(pos&(-pos));
}
return ans;
}
ll count_swaps(int S[]){
int N=(int)(sizeof(*S)/sizeof(S[0]))/2;
for (int i=1;i<=N*2;i++){
mp[S[i-1]]=i;
update(i,1);
}
ll ans=0;
for (int i=1;i<=N*2;i++){
if (dead[i])
continue;
int target=mp[S[i-1]*(-1)];
ans+=query(target)-query(i-1)-2;
if (S[i]>0)
ans++;
dead[i]=true;
update(i,-1);
dead[target]=true;
update(target,-1);
}
return ans;
}