Submission #423591

#	Time	Username	Problem	Language	Result	Execution time	Memory
423591		Belgutei	Arranging Shoes (IOI19_shoes)	C++17	100 / 100	245 ms	140736 KiB

shoes

#include "shoes.h"
#include<bits/stdc++.h>

using namespace std;

#define ll long long
#define ff first
#define ss second
#define pb push_back
#define mk make_pair

queue<int> q[100005];
queue<int> q1[100005];

ll ans;

int zereg[30],level;
vector<int> v[30];

void build_seg_tree(int x){
	zereg[0]=1;
	for(int i=0; i<=30; i++){
		if(zereg[i]>=x){
			level=i;
			break;
		}
		zereg[i+1]=zereg[i]*2;
	}
	for(int i=0; i<x; i++){
		v[level].pb(1);
	}
	for(int i=x; i<zereg[level]; i++){
		v[level].pb(0);
	}
	for(int i=level-1; i>=0; i--){
		for(int j=1; j<v[i+1].size(); j+=2){
			v[i].pb(v[i+1][j]+v[i+1][j-1]);
		}
	}
}

void del(int x){
	v[level][x]--;
	for(int i=level-1; i>=0; i--){
		x/=2;
		v[i][x]=v[i+1][x*2]+v[i+1][x*2+1];
	}
}

int bet(int k, int x, int mn, int mx){
	int y=zereg[level-k]*x;
	int z=zereg[level-k]*(x+1)-1;
	if(mn<=y && z<=mx){
		return v[k][x];
	}
	if(mx<y || mn>z || k==level) return 0;
	int ret=0;
	ret+=bet(k+1,x*2,mn,mx);
	ret+=bet(k+1,x*2+1,mn,mx);
	return ret;
}

long long count_swaps(std::vector<int> s){
	for(int i=0; i<s.size(); i++){
		if(s[i]<0){
			q[abs(s[i])].push(i);
		}
		else{
			q1[s[i]].push(i);
		}
	}
	build_seg_tree(s.size());
	for(int i=0; i<s.size(); i++){
		if(v[level][i]==0) continue;
		if(s[i]<0){
			int pos=q1[abs(s[i])].front();
			q1[abs(s[i])].pop();
			q[abs(s[i])].pop();
			del(i);
			del(pos);
			ans+=bet(0,0,i,pos);
		}
		else{
			int pos=q[s[i]].front();
			q[s[i]].pop();
			q1[s[i]].pop();
			del(pos);
			ans+=bet(0,0,i,pos);
			del(i);
		}
	}
	return ans;
}

Compilation message (stderr)

shoes.cpp: In function 'void build_seg_tree(int)':
shoes.cpp:36:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |   for(int j=1; j<v[i+1].size(); j+=2){
      |                ~^~~~~~~~~~~~~~
shoes.cpp: In function 'long long int count_swaps(std::vector<int>)':
shoes.cpp:64:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |  for(int i=0; i<s.size(); i++){
      |               ~^~~~~~~~~
shoes.cpp:73:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |  for(int i=0; i<s.size(); i++){
      |               ~^~~~~~~~~

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