| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 851654 | pomuchle | Roller Coaster Railroad (IOI16_railroad) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include "railroad.h"
#ifdef DEBUG
#include <cstdio>
#include <cassert>
int main() {
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
#include <ios>
#include <vector>
#include <functional>
#include <set>
#define REP(i, n) for(int i=0; i<(n); ++i)
#define FOR(i, p, n) for(int i=(p); i<=(n); ++i)
#define V std::vector
#define sz(A) (int(A.size()))
typedef long long ll;
typedef V <int> vi;
typedef V <ll> vll;
typedef V <bool> vb;
ll plan_roller_coaster(vi s, vi t) {
int n = sz(s);
assert(n<=16);
vb czy(n, 0);
struct ziom{
int o,w,i;
ziom(){}
ziom(int no, int nw, int ni){o=no,w=nw,i=ni;}
ziom(int j){o=w=i=j;}
};
V <ziom> z(n);
REP(i, n)
z[i]={s[i], t[i], i};
auto ogrcmp=[](const ziom &i, const ziom &j){return i.o<j.o;};
auto wyjcmp=[](const ziom &i, const ziom &j){return i.w<j.w;};
std::multiset <ziom, decltype(ogrcmp)> os(ogrcmp);
std::multiset <ziom, decltype(wyjcmp)> ws(wyjcmp);
os.insert(z.begin(), z.end());
ws.insert(z.begin(), z.end());
ziom l=z[0],p=l;
czy[0]=1;
while (1){ // dodajemy z prawej
auto itr=os.upper_bound(ziom(p.w));
while (itr!=os.begin()&&czy[std::next(itr, -1)->i])
--itr,itr=os.erase(itr, itr);
if (itr==os.begin())
break;
--itr;
p=*itr;
os.erase(itr);
czy[p.i]=1;
}
while (1){ // dodajemy z lewej
auto itr=ws.upper_bound(l.o);
while (itr!=ws.begin()&&czy[std::next(itr, -1)->i])
--itr,itr=ws.erase(itr, itr);
if (itr==ws.begin())
break;
--itr;
l=*itr;
ws.erase(itr);
czy[l.i]=1;
}
REP(i, n)
if (!czy[i])
return 1;
return 0;
}