Submission #784907

#	Time	Username	Problem	Language	Result	Execution time	Memory
784907		GusterGoose27	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	67 ms	7568 KiB

railroad

#include "railroad.h"

#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> pii;
typedef long long ll;

const int MAXN = 2e5+5;
const int MAXM = 1e9+5;
int nxt[MAXN];
int n;

ll plan_roller_coaster(vector<int> s, vector<int> t) {
    vector<pii> left, right;
    n = s.size();
    right.push_back(pii(1, 0));
    left.push_back(pii(MAXM, n+1));
    for (int i = 0; i < n; i++) {
        left.push_back(pii(s[i], i+1));
        right.push_back(pii(t[i], i+1));
    }
    sort(left.begin(), left.end());
    sort(right.begin(), right.end());
    // s.push_back(MAXM);
    // t.push_back(1);
    // sort(s.begin(), s.end());
    // sort(t.begin(), t.end());
    for (int i = 0; i < n+1; i++) {
        if (right[i].first > left[i].first) return 1;
        nxt[right[i].second] = left[i].second;
    }
    int vis = 0;
    int cur = 0;
    do {
        vis++;
        cur = nxt[cur];
    } while (cur < n+1);
    return (vis < n+1);
}

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