Submission #1188176

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

railroad

#include "railroad.h"
#include <bits/stdc++.h>
#define fi first
#define se second
#define maxn 200005
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;}

struct node {
    int S, T, idx;
    node() {}
    node(int _S, int _T, int _idx) : S(_S), T(_T), idx(_idx) {}

    bool operator < (const node &other) const {
        if (S != other.S) return S < other.S;
        if (T != other.T) return T < other.T;
        return idx < other.idx;
    }
};


long long plan_roller_coaster(vector<int> s, vector<int> t) {
    int n = s.size();
    set<node> a, b;
    for (int i = 0; i < n; i++)
        if (s[i] <= t[i]) a.insert({s[i], t[i], i});
        else b.insert({s[i], t[i], i});

    int last = INT_MIN;
    while (1) {
        if (a.empty()) break;
        auto it = a.lower_bound(node(last, 0, 0));
        if (it == a.end()) {
            if (b.empty()) break;
            auto ti = b.lower_bound(node(last, 0, 0));
            if (it == b.end()) break;
            auto [S, T, idx] = *ti;
            b.erase(ti);
            last = T;
            continue;
        }
        int nexS = it->S;
        auto ti = b.lower_bound(node(last, 0, 0));
        if (ti != b.end() && ti->S < it->T) {
            b.erase(ti);
            last = ti->T;
            continue;
        }
        last = it->S;
        a.erase(it);
    }
    return !a.empty();
}

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