Submission #289383

#	Time	Username	Problem	Language	Result	Execution time	Memory
289383		Saboon	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	217 ms	8296 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 4e5 + 10;
int go[maxn], back[maxn];

ll plan_roller_coaster(vector<int> s, vector<int> t){
	int n = (int)s.size();
	vector<int> C;
	for (int i = 0; i < n; i++)
		C.push_back(s[i]), C.push_back(t[i]);
	sort(C.begin(),C.end());
	C.resize(unique(C.begin(),C.end())-C.begin());
	ll ret = 0;
	for (int i = 0; i < n; i++){
		int pre = lower_bound(C.begin(),C.end(),s[i]) - C.begin();
		int nex = lower_bound(C.begin(),C.end(),t[i]) - C.begin();
		if (pre < nex)
			go[pre] ++, go[nex] --;
		if (nex < pre)
			back[nex] ++, back[pre] --;
	}
	for (int i = 1; i < C.size(); i++)
		go[i] += go[i-1], back[i] += back[i-1];
	for (int it = 0; it+1 < C.size(); it++){
		int i = C[it], j = C[it+1];
		ret += (j-i)*max(0,go[it]-back[it+1]-1);
	}
	return ret;
}

Compilation message (stderr)

railroad.cpp: In function 'll plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:24:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |  for (int i = 1; i < C.size(); i++)
      |                  ~~^~~~~~~~~~
railroad.cpp:26:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |  for (int it = 0; it+1 < C.size(); it++){
      |                   ~~~~~^~~~~~~~~~

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