| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 201391 | Fasho | 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 <bits/stdc++.h>
#define N 100005
#define ll long long int
#define MP make_pair
#define pb push_back
#define ppb pop_back
#define sp " "
#define endl "\n"
#define fi first
#define se second
#define ii pair<int,int>
#define lli pair<ll,ll>
#define fast cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(false)
#define fast2 freopen ("badhair.gir","r",stdin);freopen ("badhair.cik","w",stdout);
#define mod 1000000007
#define fs(x,y) for(ll i=1;i<=y;i++) cin>>x[i]
#define fo(i,x,y) for(ll i=x;i<=y;i++)
#define INF 1000000000005
#define ull unsigned long long int
#define ppf pop_front
using namespace std;
ll n,m,ar[N],sum,t,mark[N],tree[6*N],lazy[6*N];
queue<int> q[3][N];
void pre()
{
for(int i=1;i<=n;i++)
{
if(ar[i]>0)
q[1][ar[i]].push(i);
else
q[0][-ar[i]].push(i);
}
}
void build(int ind,int l,int r)
{
if(l==r)
{
tree[ind]=l;
return;
}
int mid=(l+r)/2;
build(ind*2,l,mid);
build(ind*2+1,mid+1,r);
}
void push(int ind,int l,int r)
{
ll x=lazy[ind];
lazy[ind]=0;
tree[ind]+=x;
if(l!=r)
lazy[ind*2]+=x,lazy[ind*2+1]+=x;
}
void upd(int ind,int l,int r,int a,int b)
{
if(l>b || r<a)
return;
push(ind,l,r);
if(l>=a && r<=b)
{
lazy[ind]++;
push(ind,l,r);
return;
}
int mid=(l+r)/2;
upd(ind*2,l,mid,a,b);
upd(ind*2+1,mid+1,r,a,b);
}
ll query(int ind,int l,int r,int a,int b)
{
if(l>b || r<a)
return 0;
push(ind,l,r);
if(l>=a && r<=b)
return tree[ind];
int mid=(l+r)/2;
return query(ind*2,l,mid,a,b)+query(ind*2+1,mid+1,r,a,b);
}
// int main()
int64 count_swaps(int[] S)
{
fast;
n=sizeof(S);
for(int i=0;i<n;i++)
ar[i+1]=S[i];
// n*=2;
// fs(ar,n);
// cerr<<"HELLO"<<endl;
build(1,1,n);
pre();
for(int i=1;i<=n;i++)
{
if(mark[i])
continue;
if(ar[i]<0)
{
q[0][-ar[i]].pop();
ll x=q[1][-ar[i]].front();
mark[x]++;
cout<<i<<sp<<x<<endl;
q[1][-ar[i]].pop();
ll y=query(1,1,n,x,x);
ll z=query(1,1,n,i,i);
sum+=y-z-1;
upd(1,1,n,z+1,y);
}
else
{
q[1][ar[i]].pop();
ll x=q[0][ar[i]].front();
mark[x]++;
// cout<<i<<sp<<x<<endl;
q[0][ar[i]].pop();
ll y=query(1,1,n,x,x);
ll z=query(1,1,n,i,i);
sum+=y-z;
upd(1,1,n,z+1,y);
}
}
return sum;
// cout<<sum<<endl;
}
/* cd onedrive\desktop\kod
cls
Sinav:21-22 aralik
Aciklama: Muhtemelen 25 aralik
*/