Submission #617117

#	Time	Username	Problem	Language	Result	Execution time	Memory
617117		Je_O	Roller Coaster Railroad (IOI16_railroad)	C++17	100 / 100	210 ms	24656 KiB

railroad

#include "railroad.h"
#include<bits/stdc++.h>
#define fi first
#define se second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<int, ii> iii;

const int N = 2e5 + 5;
int par[N];

int find(int x){
    if(par[x] == x)return x;
    return par[x] = find(par[x]);
}

bool merge(int x, int y){
    x = find(x); y = find(y);
    if(x == y)return false;
    par[x] = y;
    return true;
}

ll plan_roller_coaster(vector<int> s, vector<int> t){
    int n = s.size();
    s.pb(1e9); t.pb(1);
    vector<iii> v;
    for(int i = 0; i <= n; ++i){
        v.pb(mp(s[i], mp(1, i)));
        v.pb(mp(t[i], mp(-1, i)));
    }
    sort(v.begin(), v.end());
    for(int i = 0; i <= n; ++i)par[i] = i;
    vector<iii> lst;
    ll ans = 0, cur = 0;
    for(int i = 0; i < v.size() - 1; ++i){
        cur += v[i].se.fi;
        ans += max(0LL, (ll)cur) * (v[i + 1].fi - v[i].fi);
        lst.pb(mp(v[i + 1].fi - v[i].fi, mp(v[i].se.se, v[i + 1].se.se)));
        if(v[i + 1].fi == v[i].fi || cur != 0){
            merge(v[i].se.se, v[i + 1].se.se);
        }
    }
    sort(lst.begin(), lst.end());
    for(int i = 0; i < lst.size(); ++i){
        if(merge(lst[i].se.fi, lst[i].se.se)){
            ans += lst[i].fi;
        }
    }
    return ans;
}

Compilation message (stderr)

railroad.cpp: In function 'll plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:39:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   39 |     for(int i = 0; i < v.size() - 1; ++i){
      |                    ~~^~~~~~~~~~~~~~
railroad.cpp:48:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   48 |     for(int i = 0; i < lst.size(); ++i){
      |                    ~~^~~~~~~~~~~~

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