Submission #423549

#	Time	Username	Problem	Language	Result	Execution time	Memory
423549		vanic	Roller Coaster Railroad (IOI16_railroad)	C++14	30 / 100	198 ms	18248 KiB

railroad

#include "railroad.h"
#include <algorithm>
#include <cmath>
#include <vector>
#include <iostream>
#include <set>

using namespace std;
typedef long long ll;

const int maxn=2e5+5;

int n;
pair < int, int > a[maxn];
pair < int, int > b[maxn];
int pos[maxn];
bool bio[maxn];


ll plan_roller_coaster(vector < int > ss, vector < int > t){
	n=ss.size();
	for(int i=0; i<n; i++){
		a[i]={ss[i], i};
		b[i]={t[i], i};
	}
	sort(a, a+n);
	sort(b, b+n);
	for(int i=0; i<n; i++){
		pos[a[i].second]=i;
	}
/*	for(int i=0; i<n; i++){
		cout << a[i] << ' ';
	}
	cout << endl;
	for(int i=0; i<n; i++){
		cout << b[i] << ' ';
	}
	cout << endl;*/
	int ind1=0, ind2=0;
	ll sol=0;
	set < int > s;
	s.insert((int)1e9);
	while(ind1<n || ind2<n){
		if(ind1==n || (ind2!=n && a[ind1].first>=b[ind2].first)){
			s.insert(pos[b[ind2].second]);
			ind2++;
		}
		else{
//			cout << ind1 << ' ' << ind2 << endl;
			if(s.empty() || (s.size()==1 && *s.begin()==ind1)){
//				cout << "uso" << endl;
				if(b[ind2].second==a[ind1].second){
					bio[ind2+1]=1;
					sol+=b[ind2+1].first-a[ind1].first;
				}
				else{
					sol+=b[ind2].first-a[ind1].first;
					ind2++;
				}
			}
			else{
				if(*s.begin()==ind1){
					s.erase(++s.begin());
				}
				else{
					s.erase(s.begin());
				}
			}
			ind1++;
		}
		while(ind2<n && bio[ind2]){
			ind2++;
		}
	}
	return sol;
}


//g++ -std=c++17 -Wshadow -Wall -o "%e" "%f" -g -fsanitize=address -fsanitize=undefined -D_GLIBCXX_DEBUG

• Subtask 1: 0 / 11
• Subtask 2: 0 / 23
• Subtask 3: 30 / 30
• Subtask 4: 0 / 36