Submission #209940

#	Time	Username	Problem	Language	Result	Execution time	Memory
209940		anonymous	Roller Coaster Railroad (IOI16_railroad)	C++14	30 / 100	778 ms	25744 KiB

railroad

#include "railroad.h"
#include <map>
#include <set>
#include <utility>
#define MAXN 200005
using namespace std;
multiset<pair<int,int> > R, R2, R3; // [t,s], [s,t], [t,s]
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    int N = (int) s.size();
    for (int i=0; i<N; i++) {
        R.insert({t[i], s[i]});
        R2.insert({s[i], t[i]});
    }
    R.insert({1, 1<<30});
    R2.insert({1<<30, 1});
    while (R.size() > 1) {
        pair<int,int>  cur = *R.rbegin();
        R.erase(--R.end());
        if (R2.find({cur.second, cur.first}) != R2.end()) {
            R2.erase(R2.find({cur.second, cur.first}));
        } else {
            R3.erase(R3.find(cur));
        }
        while (R2.size() && (*R2.rbegin()).first >= cur.first) {
            R3.insert({(*R2.rbegin()).second,(*R2.rbegin()).first});
            R2.erase(--R2.end());
        }
        if (R3.size()) {
            R.erase(*R3.rbegin());
            R.insert({(*R3.rbegin()).first, cur.second});
            R2.insert({cur.second, (*R3.rbegin()).first});
            R3.erase(--R3.end());
        } else {
            return(42069);
        }
    }
    return(0);
}

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