Submission #568204

#	Time	Username	Problem	Language	Result	Execution time	Memory
568204		definitelynotmee	Shortcut (IOI16_shortcut)	C++98	0 / 100	2086 ms	212 KiB

shortcut

#include<bits/stdc++.h>
using namespace std;
#define ff first
#define ss second
#define all(x) x.begin(),x.end()
using ll = long long;
using pii = pair<int,int>;
using pll = pair<ll,ll>;
template<typename T>
using matrix = vector<vector<T>>;

struct seg{
    ll l, r;
    void intersect(seg b){
        l = max(l,b.l);
        r = min(r,b.r);
    }
};
struct smartstack{
    vector<pll> v;
    ll lz = 0;
    void add(ll x){
        lz+=x;
    }
    void push(pll x){
        x.ff-=lz;
        while(v.size() && v.back().ff <= x.ff)
            v.pop_back();
        v.push_back(x);
    }
    pll top(){
        if(v.empty())
            return {-1,-1};
        return {v.back().ff+lz,v.back().ss};
    }
    void pop(){
        v.pop_back();
    }
    pll operator[](int id){
        return {v[id].ff+lz,v[id].ss};
    }
    int size(){
        return v.size();
    }
};

ll find_shortcut(int n, vector<int> dist, vector<int> extra, int c){
    vector<ll> pref(n);
    for(int i = 1; i < n; i++){
        pref[i] = dist[i-1]+pref[i-1];
    }
    vector<ll> bigl(n), bigr(n);
    bigl[0] = extra[0];
    bigr[n-1] = extra[n-1]; 
    for(int i = 1; i < n; i++){
        bigl[i] = max(bigl[i-1]+dist[i-1],(ll)extra[i]);
    }
    for(int i = n-2; i >= 0; i--){
        bigr[i] = max(bigr[i+1]+dist[i],(ll)extra[i]);
    }
    vector<ll> pairl(n), pairr(n);
    for(int i = 1; i < n; i++)
        pairl[i] = max(pairl[i-1],bigl[i-1]+extra[i]+dist[i-1]);
    for(int i = n-2; i >= 0; i--)
        pairr[i] = max(pairr[i+1],bigr[i+1]+extra[i]+dist[i]);

    // for(int i = 0; i < n;  i++)
    //     cout <<   bigl[i] << ' ';
    // cout << '\n';
    // for(int i = 0; i < n;  i++)
    //     cout <<   bigr[i] << ' ';
    // cout << '\n';
    // for(int i = 0; i < n;  i++)
    //     cout <<   pairl[i] << ' ';
    // cout << '\n';
    // for(int i = 0; i < n;  i++)
    //     cout <<   pairr[i] << ' ';
    // cout << '\n';
    auto test =[&](ll x)->bool{
        int minr = n;
        while(minr > 0){
            if(pairr[minr-1] <= x)
                minr--;
            else break;
        }
        bool ok = minr == 0;
        for(int l = 0; l < n-1 && pairl[l] <= x && !ok; l++){
            while(minr <  n && min(pref[minr]-pref[l],(ll)c) + bigl[l] + bigr[minr]  > x)
                minr++;
            if(minr == n)
                break;
            int r  = minr;
            for(int i =  l + 1; i  <  r; i++){
                while(r < n && min(pref[r]-pref[i],pref[i]-pref[l]+c) + extra[i] + bigr[r] > x)
                    r++;
            }
            //cout << x <<  "->" << l <<  ' '  << r << '\n';
            if(r ==  n)
                continue;
            smartstack st, stvolta;
            st.push({bigl[l],l});
            stvolta.push({bigl[l],l});
            bool curok=1;
            for(int i = l+1; i <= r; i++){
                st.add(dist[i-1]);
                int unsat1 = -1, unsat2 = st.size()-1;
                while(unsat1 !=unsat2){
                    int m = (unsat1 + unsat2+1)>>1;
                    if(st[m].ff+extra[i] > x)
                        unsat1 = m;
                    else unsat2 = m-1;
                }
                int sat1 = -1, sat2 = stvolta.size()-1;
                while(sat1 !=sat2){
                    int m = (sat1 + sat2+1)>>1;
                    if(stvolta[m].ff+extra[i]+pref[r]-pref[i] <= x)
                        sat1 = m;
                    else sat2 = m-1;
                }
                if(unsat1 == -1 || (sat1 != -1 && st[unsat1].ss <= stvolta[sat1].ss)){
                    st.push({extra[i],i});
                    stvolta.push({extra[i]+pref[i]-pref[l],i});
                } else{
                    //cout << st[unsat1].ss << ' ' << stvolta[sat1].ss << '\n';
                    curok = 0;
                    break;
                }
                
            }
            ok  |= curok;
        }
        return ok;
    };

    ll ini = *max_element(all(extra)), fim = pairl[0];
    while(ini!=fim){
        ll m = (ini+fim)>>1;
        
        if(test(m)){
            fim = m;
        } else ini = m+1;
    }
    return ini;
}

• Subtask 1: 0 / 9
• Subtask 2: 0 / 14
• Subtask 3: 0 / 8
• Subtask 4: 0 / 7
• Subtask 5: 0 / 33
• Subtask 6: 0 / 22
• Subtask 7: 0 / 4
• Subtask 8: 0 / 3