Submission #1188173

#	Time	Username	Problem	Language	Result	Execution time	Memory
1188173		anmattroi	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	118 ms	14460 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
using ii = pair<int, int>;

template <class T> inline constexpr void cmin(T &x, const T &y) {if (x > y) x = y;}

long long plan_roller_coaster(vector<int> s, vector<int> t) {
    int n = s.size();

    vector<ii> a, b;

    for (int i = 0; i < n; i++) {
        if (s[i] <= t[i]) a.emplace_back(s[i], t[i]);
        else b.emplace_back(s[i], t[i]);
    }
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    set<ii> q;

    int sz = a.size(), tsz = b.size();

    for (int i = 0; i < tsz; i++) q.insert(ii{b[i].se, i});

    for (int i = 0, it = 0; i < sz-1; i++)
        if (a[i].se > a[i+1].fi) {
            while (it < tsz && b[it].fi < a[i].se) {
                q.erase(ii{b[it].se, it});
                ++it;
            }
            if (q.empty()) return 1;
            auto it = q.upper_bound(ii{a[i+1].fi, INT_MAX});
            if (it == q.begin()) return 1;
            q.erase(q.lower_bound(ii{(--it)->fi, 0}));
        }
    return 0;
}

Compilation message (stderr)

railroad.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~
railroad_c.h:1:9: warning: #pragma once in main file
    1 | #pragma once
      |         ^~~~

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