Submission #1190248

#	Time	Username	Problem	Language	Result	Execution time	Memory
1190248		meisgood	Arranging Shoes (IOI19_shoes)	C++20	50 / 100	172 ms	149276 KiB

shoes

#include "shoes.h"
#include <bits/stdc++.h>
using namespace std ;
#define int long long
struct segtree{
	int seg[200003] ;
	void build(int id,int l,int r){
		if (l==r) seg[id]=0 ;
		else {
			int md=(l+r)/2 ;
			build(id*2,l,md) ;
			build(id*2+1,md+1,r) ;
			seg[id]=0 ;
		}
	}
	void upd(int id,int l,int r,int x,int v){
		if (l==r&&l==x){
			seg[id]=v ;
		}
		else if (l>x||r<x) return ;
		else {
			int md=(l+r)/2 ;
			upd(id*2,l,md,x,v) ;
			upd(id*2+1,md+1,r,x,v) ;
			seg[id]=seg[id*2]+seg[id*2+1] ;
		}
	}
	int query(int id,int l,int r,int ql,int qr){
		if (ql<=l&&r<=qr) return seg[id] ;
		else if (l>qr||r<ql) return 0 ;
		else {
			int md=(l+r)/2 ;
			return query(id*2,l,md,ql,qr)+query(id*2+1,md+1,r,ql,qr) ;
		}
	}
} sss ;
bool used[200003] ;
long long count_swaps(std::vector<signed> arrr) {
	vector <int> arr ;
	for (auto x : arrr) arr.push_back(x) ;
	int n=arr.size() ;
	int i,j ;
	arr.insert(arr.begin(),0) ;
	map<int,queue <int>> q ;
	for (i = 1 ; i <= n ; i ++){
		q[arr[i]].push(i) ;
	}
	sss.build(1,1,n) ;
	for (i = 1 ; i <= n ; i ++) sss.upd(1,1,n,i,1) ;
	int tt=0 ;
	for (i = 1 ; i <= n ; i ++){
		if (used[i]) continue ;
		int x=arr[i] ;
		if (x<0){
			int pos=q[-x].front() ;
			tt+=sss.query(1,1,n,i+1,pos-1) ;
			used[pos]=1 ;
			sss.upd(1,1,n,pos,0) ;
			q[-x].pop() ;
			q[x].pop() ;
		}
		else {
			int pos=q[-x].front() ;
			tt+=sss.query(1,1,n,i+1,pos-1) ;
			used[pos]=1 ;
			sss.upd(1,1,n,pos,0) ;
			q[-x].pop() ;
			q[x].pop() ;
			tt++ ;
		}
	}
	return tt;
}

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