Submission #1020751

#	Time	Username	Problem	Language	Result	Execution time	Memory
1020751		vjudge1	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	216 ms	17988 KiB

railroad

#include <bits/stdc++.h>
#define ent '\n'
#define f first
#define s second

typedef long long ll;
using namespace std;
const int maxn = 2e5+12;

int mxs[maxn*4];
int mxt[maxn*4];
int ps[maxn*4];
int pt[maxn*4];
int s[maxn];
int t[maxn];
int p[maxn];
int n;

void upd(int v, int tl, int tr, int pos, int x, int y){
    if(tl == tr){
        ps[v] = pt[v] = tl;
        mxs[v] = x;
        mxt[v] = y;
    }
    else{
        int mid = tl + tr >> 1;
        if(pos <= mid){
            upd(v*2, tl, mid, pos, x, y);
        }
        else{
            upd(v*2+1, mid+1, tr, pos, x, y);
        }
        mxs[v] = max(mxs[v*2], mxs[v*2+1]);
        mxt[v] = max(mxt[v*2], mxt[v*2+1]);
        ps[v] = ps[v*2], pt[v] = pt[v*2];
        if(mxs[v] == mxs[v*2+1]){
            ps[v] = ps[v*2+1];
        }
        if(mxt[v] == mxt[v*2+1]){
            pt[v] = pt[v*2+1];
        }
    }
}

pair<int, int> get(int v, int tl, int tr, int l, int r, int t){
    if(tl > r || l > tr){
        return {0, 0};
    }
    if(tl >= l && tr <= r){
        if(t) return {mxt[v], pt[v]};
        return {mxs[v], ps[v]};
    }
    int mid = tl + tr >> 1;
    return max(get(v*2, tl, mid, l, r, t), get(v*2+1, mid+1, tr, l, r, t));
}

long long plan_roller_coaster(vector<int> S, vector<int> T){
    n = S.size();
    for(int i=0;i<n;i++){
        p[i] = i;
        s[i] = S[i], t[i] = T[i];
    }
    sort(p, p+n, [](int i, int j){
        return t[i] < t[j];
    });
    sort(t, t+n);
    for(int i=0;i<n;i++){
        s[i] = S[p[i]];
    }
    for(int i=1;i<=n;i++){
        upd(1, 1, n, i, s[i-1], t[i-1]);
    }
    int val = 2e9;
    for(int it=0;it<n;it++){
        int pos = 0;
        for(int l=1, r=n; l<=r;){
            int mid = l + r >> 1;
            if(t[mid-1] <= val){
                pos = mid;
                l = mid + 1;
            }
            else r = mid - 1;
        }
        auto x = get(1, 1, n, 1, pos, 0), y = get(1, 1, n, 1, pos, 1);
        if(x.s == 0){
            return 1;
        }
        if(x.f < y.f){
            val = get(1, 1, n, y.s, y.s, 0).f;
            upd(1, 1, n, y.s,  0, 0);
        }
        else{
            val = x.f;
            upd(1, 1, n, x.s, 0, 0);
        }
    }
    return 0;
}

Compilation message (stderr)

railroad.cpp: In function 'void upd(int, int, int, int, int, int)':
railroad.cpp:26:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |         int mid = tl + tr >> 1;
      |                   ~~~^~~~
railroad.cpp: In function 'std::pair<int, int> get(int, int, int, int, int, int)':
railroad.cpp:53:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   53 |     int mid = tl + tr >> 1;
      |               ~~~^~~~
railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:77:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   77 |             int mid = l + r >> 1;
      |                       ~~^~~

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