Submission #982488

#	Time	Username	Problem	Language	Result	Execution time	Memory
982488		MarwenElarbi	Roller Coaster Railroad (IOI16_railroad)	C++17	0 / 100	136 ms	14932 KiB

railroad

#include<bits/stdc++.h>
using namespace std;
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
#define fi first
#define se second
#define ll long long
#define pb push_back
const int nax=2e5+5;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
pair<ll,ll> segtree[nax*4];
vector<pair<ll,ll>> tab(nax);
void build(int pos,int l,int r){
    if(l==r){
        segtree[pos]={tab[l].se,l};
        return;
    }
    int mid=(r+l)/2;
    build(pos*2+1,l,mid);
    build(pos*2+2,mid+1,r);
    segtree[pos]=min(segtree[pos*2+1],segtree[pos*2+2]);
}
void update(int pos,int l,int r,int index){
    if(l==r){
        segtree[pos]={1e18,l};
        return;
    }
    int mid=(r+l)/2;
    if(index<=mid) update(pos*2+1,l,mid,index);
    else update(pos*2+2,mid+1,r,index);
    segtree[pos]=min(segtree[pos*2+1],segtree[pos*2+2]);
}
pair<ll,int> query(int pos,int l,int r,int left,int right){
    if(l>r||l>right||r<left) return {1e18,1e18};
    if(l>=left&&r<=right){
        return segtree[pos];
    }
    int mid=(r+l)/2;
    return min(query(pos*2+1,l,mid,left,right),query(pos*2+2,mid+1,r,left,right));
}
long long plan_roller_coaster(std::vector<int> s, std::vector<int> t) {
    int n = (int)s.size();
    tab.resize(n);
    for (int i = 0; i < n; ++i)
    {
        tab[i]={s[i],t[i]};
    }
    sort(tab.begin(),tab.end());
    int cnt=0;
    ll x=1;
    build(0,0,n-1);
    while(cnt<n){
        int cur=lower_bound(tab.begin(),tab.end(),make_pair(x,1ll*0))-tab.begin();
        if(cur==tab.size()) break;
        //cout <<x<<" "<<cur<<endl;
        auto ne=query(0,0,n-1,cur,n-1);
        //cout <<ne.fi<<endl;
        if(ne.fi==1e18) break;
        update(0,0,n-1,ne.se);
        x=tab[ne.se].se;
        cnt++;
    }
    if(cnt>=n) return 0;
    else return 1;
}
/*int main(){
    #ifndef ONLINE_JUDGE
        freopen("input.txt", "r", stdin);
        freopen("output.txt", "w", stdout);
    #endif
    int n;
    assert(1 == scanf("%d", &n));
    std::vector<int> s(n), t(n);
    for (int i = 0; i < n; ++i)
        assert(2 == scanf("%d%d", &s[i], &t[i]));
    long long ans = plan_roller_coaster(s, t);
    printf("%lld\n", ans);
    return 0;
}*/

Compilation message (stderr)

railroad.cpp: In function 'long long int plan_roller_coaster(std::vector<int>, std::vector<int>)':
railroad.cpp:54:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |         if(cur==tab.size()) break;
      |            ~~~^~~~~~~~~~~~

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