Submission #1238897

#	Time	Username	Problem	Language	Result	Execution time	Memory
1238897		MarwenElarbi	Nile (IOI24_nile)	C++20	6 / 100	64 ms	7356 KiB

nile

#include <bits/stdc++.h>
using namespace std;
#define fi first
#define se second
#define pb push_back
const int nax = 1e5+5;
long long dp[nax];
set<pair<int,int>> st;
int a[nax],b[nax];
int segtree[nax*4];
void build(int pos,int l,int r){
    if(l==r){
        segtree[pos]=a[l]-b[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]);
}
int query(int pos,int l,int r,int left,int right){
    if(l>r||r<left||l>right) return 1e9;
    if(left<=l&&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));
}
std::vector<long long> calculate_costs(std::vector<int> W, std::vector<int> A,
                                       std::vector<int> B, std::vector<int> E) {
    int n=A.size();
    int q=E.size();
    st.insert({0,n-1});
    vector<pair<int,pair<int,int>>> tab(n);
    vector<long long> answer(q);
    for (int i = 0; i < n; ++i) tab[i]={W[i],{A[i],B[i]}};
    sort(tab.begin(),tab.end());
    st.insert({n,n});
    vector<pair<int,int>> split;
    long long ans=0;
    for (int i = 0; i < n; ++i)
    {
        W[i]=tab[i].fi;
        A[i]=tab[i].se.fi;
        B[i]=tab[i].se.se;
        ans+=B[i];
        if(i<n-1) split.push_back({W[i+1]-W[i],i});
        a[i]=A[i];
        b[i]=B[i];
    }
    sort(split.begin(),split.end(),greater<pair<int,int>>());
    vector<pair<int,int>> nabba;
    for (int i = 0; i < q; ++i) nabba.push_back({E[i],i});
    sort(nabba.begin(),nabba.end(),greater<pair<int,int>>());
    int j=0;
    build(0,0,n-1);
    if(n%2) ans+=query(0,0,n-1,0,n-1);
    for (int i = 0; i < q; ++i)
    {
        int d=nabba[i].fi;
        while(j<split.size()&&split[j].fi>d){
            pair<int,int> cur = *--st.upper_bound({split[j].se,n});
            pair<int,int> nab = *st.upper_bound({split[j].se,0});
            st.erase(cur);
            if((cur.se-cur.fi+1)%2) ans-=query(0,0,n-1,cur.fi,cur.se);
            if(cur.fi!=split[j].se) st.insert({cur.fi,split[j].se});
            if(split[j].se+1!=cur.se) st.insert({split[j].se+1,cur.se});
            if((split[j].se-cur.fi+1)%2) ans+=query(0,0,n-1,cur.fi,split[j].se);
            if((cur.se-split[j].se)%2) ans+=query(0,0,n-1,split[j].se+1,cur.se);
            j++;
        }
        answer[nabba[i].se]=ans;
    }
    return answer;
}

• Subtask 0: 0 / 0
• Subtask 1: 6 / 6
• Subtask 2: 0 / 13
• Subtask 3: 0 / 17
• Subtask 4: 0 / 11
• Subtask 5: 0 / 20
• Subtask 6: 0 / 15
• Subtask 7: 0 / 18