Submission #826829

#	Time	Username	Problem	Language	Result	Execution time	Memory
826829		vjudge1	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	139 ms	58468 KiB

shoes

#include <bits/stdc++.h>
#include "shoes.h"
#define f first
#define s second 
#define ent '\n'
//#define int long long

//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
//#pragma GCC optimize("Ofast,unroll-loops,fast-math,O3")

//typedef long double ld;
typedef long long ll;
using namespace std;
 
struct node{double x,y;};
//double len(node a,node b)
//{return sqrt((a.x-b.x)*(a.x-b.y)+(a.y-b.y)*(a.x-b.y));}

struct seg{
	int m1,m2,sum,cnt;
};

const string out[2]={"No\n","Yes\n"};
const ll dx[]={0,0,1,-1,-1,1,1,-1};  
const ll dy[]={1,-1,0,0,-1,1,-1,1};
const int md=998244353;
const int mod=1e9+7;
const int mx=1e6+1; 
const int tst=1e5;
const bool T=0;

vector<int> g[mx];
vector<int> e[mx];
int t[mx*4];
int a[mx];
int b[mx];
int n,m,k;

void upd(int v,int tl,int tr,int pos,int x){
	if(tl==tr){
		t[v]=x;
	}
	else{
		int mid=tl+tr>>1;
		if(pos<=mid){
			upd(v*2,tl,mid,pos,x);
		}
		else{
			upd(v*2+1,mid+1,tr,pos,x);
		}
		t[v]=t[v*2]+t[v*2+1];
	}
}

int get(int v,int tl,int tr,int l,int r){
	if(tl>r || l>tr || l>r)return 0;
	if(tl>=l && tr<=r)return t[v];
	int mid=tl+tr>>1;
	return get(v*2,tl,mid,l,r)+get(v*2+1,mid+1,tr,l,r);
}

ll count_swaps(std::vector<int> S){
	n=S.size();
	for(int i=1;i<=n;i++){
		a[i]=S[i-1];
	}
	ll ans=0;
	for(int i=n;i;i--){
		if(a[i]>0){
			g[a[i]].push_back(i);
		}
		else{
			e[-a[i]].push_back(i);
		}
		upd(1,1,n,i,1);
	}
	for(int i=1;i<=n;i++){
		if(!get(1,1,n,i,i)){
			continue;
		}
		int pos=0;
		if(a[i]>0){
			pos=e[a[i]].back();
			e[a[i]].pop_back();
			g[a[i]].pop_back();
			ans+=get(1,1,n,i,pos-1);
			upd(1,1,n,pos,0);
		}
		else{
			pos=g[-a[i]].back();
			g[-a[i]].pop_back();
			e[-a[i]].pop_back();
			ans+=get(1,1,n,i+1,pos-1);
			upd(1,1,n,pos,0);
		}
	}
	return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'void upd(int, int, int, int, int)':
shoes.cpp:44:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   44 |   int mid=tl+tr>>1;
      |           ~~^~~
shoes.cpp: In function 'int get(int, int, int, int, int)':
shoes.cpp:58:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   58 |  int mid=tl+tr>>1;
      |          ~~^~~

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