Submission #264784

#	Time	Username	Problem	Language	Result	Execution time	Memory
264784		sealnot123	Roller Coaster Railroad (IOI16_railroad)	C++14	0 / 100	165 ms	6660 KiB

railroad

#include "railroad.h"
#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define SZ(a) (int)(a).size()
#define FOR(i, a, b) for(int i=(a); i<=(b); ++i)
#define ROF(i, a, b) for(int i=(a); i>=(b); --i)
#define make_unique(a) sort(all((a))), (a).resize(unique(all((a)))-(a).begin())

using namespace std;

typedef pair<int,int> PII;
typedef long long LL;
typedef double DD;
typedef long double LD;
typedef pair<LL,LL> PLL;
typedef pair<DD,DD> PDD;
typedef vector<int> VI;
typedef vector<LL> VL;

int n;
LL plan_roller_coaster(VI s, VI t) {
    int n = SZ(s);
    vector<int> p;
    vector<PII> P;
    FOR(i,0,n-1) p.pb(s[i]), P.pb(PII(s[i],t[i]));
    sort(all(P));
    sort(all(p));
    vector<int> dp(n);
    FOR(i,0,n-1){
        int idx = lower_bound(all(p), t[i])-p.begin();
        if(idx == n) continue;
        dp[idx]++;
    }
    dp[0]++;
    FOR(i,1,n-1) dp[i] += dp[i-1];
    FOR(i,0,n-1){
        int idx = lower_bound(all(p), P[i].y)-p.begin();
        //printf("(%d, %d)\n",i,idx);
        if(idx > i){
            if(dp[i] <= i) return 1;
        }else{
            if(dp[i] < i) return 1;
            if(dp[i]-1 == i && idx == i) return 1;
        }
    }
    return 0;
}

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