Submission #610944

#	Time	Username	Problem	Language	Result	Execution time	Memory
610944		PiejanVDC	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	1212 ms	78480 KiB

railroad

#include "railroad.h"
#include <bits/stdc++.h>
using namespace std;

const int mxN = (int)2e5+5;

vector<int>st(8*mxN);

int l,r,val;
vector<int>lazy(8*mxN);

int query(int i, int j, int p) {
    if(i > r || j < l)
        return 0;
    if(i >= l && j <= r)
        return st[p]+lazy[p];
    int mid = (i+j)/2;
    lazy[2*p] += lazy[p];
    lazy[2*p+1] += lazy[p];
    lazy[p] = 0;
    return query(i, mid, 2*p) + query(mid+1, j, 2*p+1);
}

void update(int i, int j, int p) {
    if(i > r || j < l)
        return;
    if(i >= l && j <= r) {
        lazy[p] += val;
        return;
    }
    int mid = (i+j)/2;
    lazy[2*p] += lazy[p];
    lazy[2*p+1] += lazy[p];
    lazy[p] = 0;
    update(i, mid, 2*p);
    update(mid+1, j, 2*p+1);
}

vector<int>adj[2*mxN];

long long plan_roller_coaster(vector<int>s, vector<int>t) {
    set<int>S;
    int n = (int)s.size();
    for(auto z : s)
        S.insert(z);
    for(auto z : t)
        S.insert(z);
    map<int,int>rev;
    auto it = S.begin();
    for(int i = 0 ; i < 2*n ; i++, it++)
        rev[*it] = i;
    for(int i = 0 ; i < n ; i++) {
        if(s[i] < t[i]) {
            auto ff = S.lower_bound(s[i]);
            auto ss = S.lower_bound(t[i]);
            ss--;
            l = rev[*ff], r = rev[*ss];
            val = 1;
            update(0, 2*n-1, 1);
        } else if(s[i] > t[i]) {
            auto ss = S.lower_bound(s[i]);
            auto ff = S.lower_bound(t[i]);
            ss--;
            l = rev[*ff], r = rev[*ss];
            val = -1;
            update(0, 2*n-1, 1);
        }
    }
    long long ret = 0;
    vector<int>in(2*n+500,0),out(2*n+500,0);
    for(int i = 0 ; i < 2*n ; i++) {
        l = r = i;
        int R = query(0, 2*n-1, 1);
        if(R > 1) {
            ret = 1;
            break;
        }
        R--;
        R = abs(R);
        if(!R) continue;
        adj[i].push_back(i+1); 
        in[i+1]+=R,out[i]+=R;
        if(i)
            adj[i].push_back(i-1), in[i-1]++,out[i]++;
    }

    if(ret)
        return 1;

    for(int i = 0 ; i < 2*n ; i++)
        if(out[i] != in[i])
            ret = 1;

    if(ret)
        return 1;

    stack<int>q;
    q.push(0);

    vector<bool>vis(2*n, 0);
    vis[0] = 1;
    while(!q.empty()) {
        int node = q.top();
        q.pop();
        for(auto z : adj[node]) if(!vis[z])
            vis[z] = 1, q.push(z);
    }

    for(auto z : vis)
        if(!z)
            ret = 1;

    return ret;
}

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