Submission #423520

#	Time	Username	Problem	Language	Result	Execution time	Memory
423520		vanic	Roller Coaster Railroad (IOI16_railroad)	C++14	0 / 100	114 ms	10608 KiB

railroad

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

using namespace std;
typedef long long ll;

const int maxn=2e5+5;

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


ll plan_roller_coaster(vector < int > s, vector < int > t){
	n=s.size();
	for(int i=0; i<n; i++){
		a[i]={s[i], i};
		b[i]={t[i], i};
	}
	sort(a, a+n);
	sort(b, b+n);
/*	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;
	int od;
	while(ind1<n || ind2<n){
		if(ind1==n || (ind2!=n && a[ind1].first>=b[ind2].first)){
			bio[b[ind2].second]=1;
			ind2++;
		}
		else{
			if(bio[a[ind1].second]){
				od=-1;
			}
			else{
				od=0;
			}
//			cout << ind1 << ' ' << ind2 << endl;
			if(ind2+od<ind1){
//				cout << "uso" << endl;
				if(b[ind2].second==a[ind1].second){
					bio[b[ind2+1].second]=1;
					sol+=b[ind2+1].first-a[ind1].first;
				}
				else{
					bio[b[ind2].second]=1;
					sol+=b[ind2].first-a[ind1].first;
					ind2++;
				}
			}
			ind1++;
		}
		while(ind2<n && bio[b[ind2].second]){
			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: 0 / 30
• Subtask 4: 0 / 36