Submission #169285

#	Time	Username	Problem	Language	Result	Execution time	Memory
169285		anubhavdhar	Arranging Shoes (IOI19_shoes)	C++14	100 / 100	487 ms	283000 KiB

shoes

#include<bits/stdc++.h>
 
#define ll long long int 
#define FOR(i,N) for(i=0;i<N;i++)
#define FORe(i,N) for(i=1;i<=N;i++)
#define FORr(i,a,b) for(i=a;i<b;i++)
#define ii pair<ll,ll>
#define vi vector<ll> 
#define vii vector<ii>
#define ff first
#define ppppppppp second 
#define mp make_pair 
#define pb push_back
 
using namespace std;
 
//#include "shoes.h"
/*
const ll MAXN = 1e5+5;
const ll INF = 1e17 + 9;
const ll MOD = 1e9 + 7;
const ll INT_BITS = 31;
const ll LOGN = 17;
*/

#define MAXN 200005

struct SegTree
{
	ll st[4*MAXN];
	void upd(ll node,ll ss,ll se,ll i)
	{
		if (i >se or i< ss)
			return;
		if (ss == se)
		{
			st[node] = 1;
			return;
		}
		ll mid = (ss+se)/2;
		upd(node*2+1,ss,mid,i);
		upd(node*2+2,mid+1,se,i);
		st[node] = st[node*2+1]+st[node*2+2];
	}
	ll quer(ll node, ll ss, ll se,ll l,ll r)
	{
		if (l>se or r<ss)
			return 0;
		if (l <= ss and r >=se)
			return st[node];
		ll mid = (ss+se)/2;
		return quer(node*2+1,ss,mid,l,r)+quer(node*2+2,mid+1,se,l,r);
	}
	SegTree()
	{
		ll i;
		FOR(i,4*MAXN)
			st[i] = 0;
	}
	inline void update(ll i)
	{
		upd(0,0,MAXN,i);
	}
	inline ll query(ll l,ll r)
	{
		return quer(0,0,MAXN,l,r);
	}
};

long long count_swaps(vector<int>s) 
{
	//cout<<"p\n";
	ll N,i,j,l,r,ans = 0;
	//cin>>N;
	N = s.size();
	SegTree S;
	ll A[N],pr[N];
	queue<ll> L[1 + N],R[N+1];
	bool rem[N];
	FOR(i,N)
	{
		A[i] = s[i];
		//cout<<"entering for i = "<<i<<endl;
		rem[i] = false;
		if (A[i] < 0) // Left shoe
		{
			if (!R[-A[i]].empty())
			{
				r = R[-A[i]].front();
				R[-A[i]].pop();
				pr[r] = i;
				pr[i] = r;
				A[i] *= -1;
				A[r] *= -1;
				ans++;
			}
			else
				L[-A[i]].push(i);
		}
		else if (A[i] > 0) // Right Shoe;
		{
			if (!L[A[i]].empty())
			{
				l = L[A[i]].front();
				L[A[i]].pop();
				pr[l] = i;
				pr[i] = l;
			}
			else
				R[A[i]].push(i);
		}
	}
    /*
	FOR(i,N)
		cout<<A[i]<<" ";
	cout<<endl;
	FOR(i,N)
		cout<<pr[i]<<" ";
	cout<<endl;
    */
	FOR(i,N)
	{
		if(A[i] < 0)
		{
			ans += pr[i]-i-1;
			ans -= S.query(i,pr[i]);
			/*for(j = i + 1;j<pr[i];j++)
				if (rem[j])
					ans--;*/
			S.update(pr[i]);
			rem[pr[i]] = true;
		}
 
	}
	return ans;
}
/*
int main()
{
	ll i,n;
	cin>>n;
	vector<int> s(2*n);
	FOR(i,2*n)
		cin>>s[i];
	//cout<<"input taken\n";
	i = count_swaps(s);
	cout<<i<<endl;
	return 0;
}*/

Compilation message (stderr)

shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:73:9: warning: unused variable 'j' [-Wunused-variable]
  ll N,i,j,l,r,ans = 0;
         ^
shoes.cpp:79:7: warning: variable 'rem' set but not used [-Wunused-but-set-variable]
  bool rem[N];
       ^~~

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