Submission #201401

#	Time	Username	Problem	Language	Result	Execution time	Memory
201401		Fasho	Arranging Shoes (IOI19_shoes)	C++14	0 / 100	155 ms	202364 KiB

shoes

#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()
int count_swaps(vector<int> S)
{
	fast;
	int a;
	int n=S.size();
	// n=int(sizeof(S)/sizeof(S[0]));
	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
*/

Compilation message (stderr)

shoes.cpp: In function 'int count_swaps(std::vector<int>)':
shoes.cpp:87:6: warning: unused variable 'a' [-Wunused-variable]
  int a;
      ^

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