제출 #785942

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
785942		GusterGoose27	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	792 ms	74920 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;
const ll inf = (ll)MAXN*MAXM;
vector<int> edges[2*MAXN];
map<int, int> conv;
int anticonv[2*MAXN];
bool vis[2*MAXN];
vector<vector<int>> visits;
vector<pii> ranges;
vector<int> cont[2*MAXN];

int n, m = 0;

void dfs(int cur) {
    //cerr << visits.size()-1 << ' ' << anticonv[cur] << '\n';
    vis[cur] = 1;
    visits.back().push_back(anticonv[cur]);
    ranges.back().first = min(ranges.back().first, anticonv[cur]);
    ranges.back().second = max(ranges.back().second, anticonv[cur]);
    for (int nxt: edges[cur]) {
        if (!vis[nxt]) dfs(nxt);
    }
}

void ins(int v) {
    if (conv.find(v) != conv.end()) return;
    conv[v] = m;
    anticonv[m++] = v;
}

ll plan_roller_coaster(vector<int> s, vector<int> t) {
    ins(1);
    ins(MAXM);
    vector<pii> events;
    events.push_back(pii(1, 0));
    events.push_back(pii(MAXM, 1));
    for (int v: s) {
        ins(v);
        events.push_back(pii(v, 1));
    }
    for (int v: t) {
        ins(v);
        events.push_back(pii(v, 0));
    }
    n = s.size();
    for (int i = 0; i < n; i++) edges[conv[s[i]]].push_back(conv[t[i]]);
    sort(events.begin(), events.end()); // 0 start, 1 end
    int sum = 0;
    ll ans = 0;
    for (int i = 0; i < events.size()-1; i++) {
        sum += events[i].second ? -1 : 1;
        if (sum < 0) {
            edges[conv[events[i+1].first]].push_back(conv[events[i].first]);
            ans += ((ll)events[i+1].first-events[i].first)*(-sum);
        }
        // //cerr << conv[events[i].first] << ' ' << sum << '\n';
        if (sum > 0) edges[conv[events[i].first]].push_back(conv[events[i+1].first]);
    }
    //cerr << ans << '\n';
    assert(conv[1] == 0);
    // vector<pii> groups;
    vector<pii> endpoints;
    for (int i = 0; i < m; i++) {
        if (vis[i]) continue;
        // if (i) return 1;
        vector<int> v; visits.push_back(v);
        ranges.push_back(pii(anticonv[i], anticonv[i]));
        dfs(i);
        int id = ranges.size()-1;
        //cerr << ranges[id].first << ' ' << ranges[id].second << '\n';
        endpoints.push_back(pii(ranges[id].first, id));
        endpoints.push_back(pii(ranges[id].second, id));
        // groups.push_back(pii(ranges.back().second-ranges.back().first, ranges.size()-1));
    }
    //cerr << ranges.size() << '\n';
    //cerr << '\n';
    // return 0;
    sort(endpoints.begin(), endpoints.end());
    vector<int> stck;
    for (pii e: endpoints) {
        int v = e.second;
        // if (stck.empty()) //cerr << v << '\n';
        if (stck.empty() || stck.back() != v) {
            if (!stck.empty()) {
                cont[stck.back()].push_back(v);
                //cerr << stck.back() << ' ' << v << '\n';
            }
            stck.push_back(v);
        }
        else {
            stck.pop_back();
        }
    }
    for (int i = 0; i < ranges.size(); i++) {
        sort(visits[i].begin(), visits[i].end());
        int p = 0;
        for (int j = 0; j < visits[i].size()-1; j++) {
            vector<int> cur_dists;
            int mx = 0;
            int prv = visits[i][j];
            while (p < cont[i].size() && ranges[cont[i][p]].first < visits[i][j+1]) {
                int curv = cont[i][p];
                ans += ranges[curv].first-prv;
                mx = max(mx, ranges[curv].first-prv);
                prv = ranges[curv].second;
                p++;
            }
            mx = max(mx, visits[i][j+1]-prv);
            ans += visits[i][j+1]-prv;
            ans -= mx;
        }
    }
    return ans;
}

컴파일 시 표준 에러 (stderr) 메시지

railroad.cpp: In function 'll plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:59:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |     for (int i = 0; i < events.size()-1; i++) {
      |                     ~~^~~~~~~~~~~~~~~~~
railroad.cpp:103:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  103 |     for (int i = 0; i < ranges.size(); i++) {
      |                     ~~^~~~~~~~~~~~~~~
railroad.cpp:106:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  106 |         for (int j = 0; j < visits[i].size()-1; j++) {
      |                         ~~^~~~~~~~~~~~~~~~~~~~
railroad.cpp:110:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  110 |             while (p < cont[i].size() && ranges[cont[i][p]].first < visits[i][j+1]) {
      |                    ~~^~~~~~~~~~~~~~~~

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