Submission #413530

#	Time	Username	Problem	Language	Result	Execution time	Memory
413530		Mamnoon_Siam	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	158 ms	9656 KiB

railroad

#ifndef LOCAL
#include "railroad.h"
#endif
#include <bits/stdc++.h>
using namespace std;

using ii = pair<int, int>;
using ll = long long;
using vi = vector<int>;
#define all(v) begin(v), end(v)
#define sz(v) (int)(v.size())
#define fi first
#define se second

ll plan_roller_coaster(vi s, vi t) {
	int n = sz(s);
	vi ps(n); iota(all(ps), 0);
	sort(all(ps), [&s](int i, int j){ return s[i] < s[j]; });
	vi swhere(n);
	for(int i = 0; i < n; ++i) {
		swhere[ps[i]] = i;
	}
	vi pt(n); iota(all(pt), 0);
	sort(all(pt), [&t,&swhere](int i, int j){
		return t[i] == t[j] ? swhere[i] > swhere[j] : t[i] < t[j];
	});
	sort(all(s));
	sort(all(t));
	int ptr = sz(s);
	for(int i = sz(t)-1; i >= 0; --i) {
		while(ptr and s[ptr-1] >= t[i]) {
			--ptr;
		}
		int S = n - i;
		int NS = n - ptr - (swhere[pt[i]] >= ptr);
		if(S - NS > 1) return 1;
	}
	return 0;
}

#ifdef LOCAL
int main() {
	freopen("01", "r", stdin);
  int n;
  assert(1 == scanf("%d", &n));
  std::vector<int> s(n), t(n);
  for (int i = 0; i < n; ++i)
    assert(2 == scanf("%d%d", &s[i], &t[i]));
  long long ans = plan_roller_coaster(s, t);
  printf("%lld\n", ans);
  return 0;
}
#endif

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