| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 535495 | makanhulia | Arranging Shoes (IOI19_shoes) | C++17 | 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 <bits/stdc++.h>
#define ll long long
#define fi first
#define se second
const ll MOD=1e9+7;
using namespace std;
ll a[200005],node[800005];
void build(ll now,ll l,ll r){
if(l==r){
node[now]=a[l];
return;
}
ll m=(l+r)/2;
build(now*2,l,m);
build(now*2+1,m+1,r);
node[now]=node[now*2]+node[now*2+1];
}
ll query(ll now,ll l,ll r,ll x,ll y){
if(l>r){
return 0;
}
if(x<=l&&r<=y){
return node[now];
}
if(y<l||x>r){
return 0;
}
ll m=(l+r)/2;
return query(now*2,l,m,x,y)+query(now*2+1,m+1,r,x,y);
}
void update(ll now,ll l,ll r,ll x,ll val){
if(r<x||x<l){
return;
}
if(l==r){
node[now]=val;
return;
}
ll m=(l+r)/2;
update(now*2,l,m,x,val);
update(now*2+1,m+1,r,x,val);
node[now]=node[now*2]+node[now*2+1];
}
map <ll,ll> mp;
ll count_swaps(vector <ll> vec){
ll N=vec.size();
ll a[200005];
for(int i=1;i<=vec.size();i++){
a[i]=vec[i-1];
}
build(1,1,N);
ll catat=0;
for(int i=1;i<=N;i++){
if(mp[-a[i]]==0){
update(1,1,N,i,1);
mp[a[i]]=i;
}
else{
if(a[i]>0){
ll r=i;
ll l=mp[-a[i]];
catat+=(r-l-1);
catat-=query(1,1,N,l+1,r-1);
mp[a[i]]=0;
mp[-a[i]]=0;
update(1,1,N,l,0);
update(1,1,N,r,0);
}
else{
ll r=i;
ll l=mp[-a[i]];
catat+=(r-l);
catat-=query(1,1,N,l+1,r-1);
mp[a[i]]=0;
mp[-a[i]]=0;
update(1,1,N,l,0);
update(1,1,N,r,0);
}
}
}
return catat;
}
//int main(){
// ll N;
// cin>>N;
// vector <ll> test;
// for(int i=1;i<=N;i++){
// ll temp;
// cin>>temp;
// test.push_back(temp);
// }
// cout<<count_swaps(test)<<endl;
//}