Submission #228288

#	Time	Username	Problem	Language	Result	Execution time	Memory
228288		computerbox	Arranging Shoes (IOI19_shoes)	C++14	50 / 100	195 ms	54776 KiB

shoes

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


#define ll long long
#define pb push_back
#define all(x) (x).begin(), (x).end()

using namespace std;


ll t[4*1000010];
ll tadd[4*1000010];

void push(ll v,ll l,ll r)
{
  if(tadd[v]!=0)
  {
	  t[v]+=tadd[v];
	  if(l!=r)
	  {
		tadd[v*2]+=tadd[v];
		tadd[v*2+1]+=tadd[v];  
	  }
	  tadd[v]=0;	  
  }	
}

void build(ll v,ll l,ll r)
{
  if(l==r)
  {
	t[v]=l;
	return ;  
  }	
  ll mid=l+(r-l)/2;
  build(v*2,l,mid);
  build(v*2+1,mid+1,r);
  t[v]=max(t[v*2],t[v*2+1]);
}

void update1(ll v,ll l,ll r,ll nac,ll konec,ll x)
{
   push(v,l,r);
   if(l>konec || r<nac)return ;
   if(l>=nac && r<=konec)
   {
	 tadd[v]+=x;
	 push(v,l,r);
	 return ;   
   }	
   ll mid=l+(r-l)/2;
   update1(v*2,l,mid,nac,konec,x);
   update1(v*2+1,mid+1,r,nac,konec,x);
   t[v]=max(t[v*2],t[v*2+1]);
}

void update2(ll v,ll l,ll r,ll pos,ll x)
{
   push(v,l,r);
   if(l==r)
   {
	 t[v]=x;
	 return ;   
   }	
   ll mid=l+(r-l)/2;
   if(pos<=mid)update2(v*2,l,mid,pos,x);
   else update2(v*2+1,mid+1,r,pos,x);
   t[v]=max(t[v*2],t[v*2+1]);
}

ll query(ll v,ll l,ll r,ll pos)
{
  push(v,l,r);
  if(l==r)
  {
	return t[v];  
  }
  ll mid=l+(r-l)/2;
  if(pos<=mid)return query(v*2,l,mid,pos);
  else return query(v*2+1,mid+1,r,pos);
}

vector<ll>leftt[100010];
vector<ll>rightt[100010];
ll used[100010];


ll count_swaps(vector<int>massiv)
{
  ll n=(ll)massiv.size();
  set<ll>nuj;
  build(1,1,n);
  for(ll i=0;i<n;i++)
  {
    if(massiv[i]<0)leftt[abs(massiv[i])].pb(i+1);
    else rightt[massiv[i]].pb(i+1);  
    nuj.insert(massiv[i]);
  }
  for(auto i:nuj)
  {
    if(i<0)reverse(all(leftt[abs(i)]));
    else reverse(all(rightt[i]));  
  }
  ll ans=0;
  for(ll i=0;i<n;i++)
  {
	if(used[i+1])continue;
    if(massiv[i]>0)
    {
	  rightt[massiv[i]].pop_back();	
	  ll pos=leftt[massiv[i]].back();
	  used[pos]=1;
	  used[i+1]=1;
	  leftt[massiv[i]].pop_back();
	  ll pos1=query(1,1,n,pos);
	  ll pos2=query(1,1,n,i+1);
	  ans+=pos1-pos2;
	  update1(1,1,n,i+2,pos-1,1);
	  update2(1,1,n,i+1,pos2+1);
	  update2(1,1,n,pos,pos2);
    }
    else if(massiv[i]<0)
    {
	  leftt[-massiv[i]].pop_back();	
	  ll pos=rightt[-massiv[i]].back();
	  used[pos]=1;
	  used[i+1]=1;
	  rightt[-massiv[i]].pop_back();
	  ll pos1=query(1,1,n,pos);
	  ll pos2=query(1,1,n,i+1);
	  ans+=((pos1-pos2)-1);
	  update1(1,1,n,i+2,pos-1,1);	
	  update2(1,1,n,pos,pos2+1);
    }  
  }
  return ans;
}

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