Submission #1306390

#	Time	Username	Problem	Language	Result	Execution time	Memory
1306390		Tesla89	Arranging Shoes (IOI19_shoes)	C++20	45 / 100	177 ms	77952 KiB

shoes

#include <bits/stdc++.h>
#define tesal ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define ain(x,n) for(int i=0;i<n;i++)cin>>x[i];
#define fi first
#define se second
#define pii pair<int,int>
#define YNOut(fun) if(fun){cout<<"YES\n";}else{cout<<"NO\n";}
#define deb(arr) {for(auto i:arr){cout<<i<<' ';}cout<<'\n';}

using namespace std;

vector<int>seg;

void push_down(int i,int l,int r)
{
	if(l==r)return;
	seg[i<<1]+=seg[i];
	seg[i<<1|1]+=seg[i];
	seg[i]=0;
}

void update(int i,int l,int r,int tl,int tr)
{
	push_down(i,l,r);
	if(l>tr||r<tl||l>r)return;
	if(l>=tl&&r<=tr){
		seg[i]++;
		push_down(i,l,r);
		return;
	}
	int mid=l+r>>1;
	update(i<<1,l,mid,tl,tr);
	update(i<<1|1,mid+1,r,tl,tr);
}

int query(int i,int l,int r,int x)
{
	push_down(i,l,r);
	if(l==r)return seg[i];
	int mid=l+r>>1;
	if(mid>=x)return query(i<<1,l,mid,x);
	return query(i<<1|1,mid+1,r,x);
}

int64_t count_swaps(const vector<int> S)
{
	int n=S.size();
	int64_t res=0;
	seg.assign(n<<2,0);
	queue<pii>qu;
	map<int,queue<int>>mp;
	for(int i=0;i<n;i++){
		if(S[i]<0)qu.push({i,S[i]});
		else mp[S[i]].push(i);
	}
	for(int i=0;i<n;i+=2)
	{
		int neg=qu.front().fi,num=qu.front().se;
		qu.pop();
		res+=neg+query(1,0,n-1,neg)-i;
		update(1,0,n-1,0,neg);
		int pos=mp[-num].front();
		mp[-num].pop();
		res+=pos+query(1,0,n-1,pos)-i-1;
		update(1,0,n-1,0,pos);
	}
	return res;
}

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