Submission #1012157

#	Time	Username	Problem	Language	Result	Execution time	Memory
1012157		hotboy2703	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	110 ms	15008 KiB

railroad

#include "railroad.h"

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
#define pll pair <ll,ll>
#define fi first
#define se second
#define MP make_pair
#define sz(a) (ll((a).size()))
#define BIT(mask,i) (((mask) >> (i))&1)
#define MASK(i) (1LL << (i))

long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    s.push_back(1e9);
    t.push_back(1);
    int n = (int) s.size();
    vector <ll> val;
    for (ll i = 0;i < n;i ++){
        val.push_back(s[i]);
        val.push_back(t[i]);
    }
    sort(val.begin(),val.end());
    val.resize(unique(val.begin(),val.end())-val.begin());
    vector <ll> cnt(sz(val));
    for (ll i = 0;i < n;i ++){
        ll l = lower_bound(val.begin(),val.end(),s[i])-val.begin();
        ll r = lower_bound(val.begin(),val.end(),t[i])-val.begin();
        cnt[l]++,cnt[r]--;
    }
    for (ll i = 1;i < sz(val);i ++){
        cnt[i] += cnt[i-1];
    }
    ll res = 0;
    for (ll i = 0;i + 1 < sz(val);i ++){
        res += max(0LL,cnt[i]) * (val[i+1]-val[i]);
    }
    return res;
}

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