Submission #946969

#	Time	Username	Problem	Language	Result	Execution time	Memory
946969		Pacybwoah	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	342 ms	30364 KiB

constellation3

#include<iostream>
#include<vector>
#include<algorithm>
#include<utility>
#include<set>
using namespace std;
typedef long long ll;
struct rng{
    ll val;
    int l,r,x,y;
    rng(ll _val,int _l,int _r,int _x,int _y){
        val=_val,l=_l,r=_r,x=_x,y=_y;
    }
};
bool operator< (const rng &a,const rng &b){
    return a.y<b.y;
}
vector<ll> bit;
void modify(int pos,ll num,int n){
    while(pos<=n){
        bit[pos]+=num;
        pos+=pos&-pos;
    }
}
ll quer(int pos){
    ll ans=0;
    while(pos>0){
        ans+=bit[pos];
        pos-=(pos&-pos);
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    ll ans=0;
    cin>>n;
    vector<int> h(n+1),bases(n+1,-1);
    bit.resize(n+1);
    for(int i=1;i<=n;i++) cin>>h[i];
    vector<vector<int>> st(19,vector<int>(n+1));
    for(int i=0;i<20;i++){
        for(int j=(1<<i);j<min(1<<(i+1),n+1);j++){
            if(bases[j]==-1) bases[j]=i;
        }
    }
    for(int i=1;i<=n;i++) st[0][i]=h[i];
    for(int i=1;i<19;i++){
        for(int j=1;j<=n;j++) st[i][j]=max(st[i-1][j],st[i-1][min(j+(1<<(i-1)),n)]);
    }
    auto query=[&](int l,int r){
        int len=bases[r-l+1];
        return max(st[len][l],st[len][r-(1<<len)+1]);
    };
    int m;
    ll c;
    cin>>m;
    vector<rng> vec;
    for(int i=0;i<m;i++){
        int x,y;
        cin>>x>>y>>c;
        ans+=c;
        int lh,rh,l=1,r=x;
        while(l<r){
            int mid=((l+r)>>1);
            if(query(mid,x)>=y) l=mid+1;
            else r=mid;
        }
        lh=l,l=x,r=n;
        while(l<r){
            int mid=((l+r)>>1)+1;
            if(query(x,mid)>=y) r=mid-1;
            else l=mid;
        }
        rh=l;
        vec.emplace_back(c,lh,rh,x,y);
    }
    sort(vec.begin(),vec.end());
    set<pair<int,int>> s;
    vector<ll> dp(m);
    int cnt=0;
    auto mod=[&](int l,int r,ll num){
        modify(l,num,n);
        modify(r+1,-num,n);
    };
    for(auto &[val,l,r,x,y]:vec){
        ll sum=0;
        while(!s.empty()){
            auto iter=s.lower_bound(make_pair(l,-1));
            if(iter==s.end()||(*iter).first>r) break;
            mod(vec[(*iter).second].l,vec[(*iter).second].r,-dp[(*iter).second]);
            sum+=dp[(*iter).second];
            s.erase(iter);
        }
        mod(l,r,sum);
        dp[cnt]=max(quer(x)+val,sum);
        cnt++;
        s.insert(make_pair(x,cnt-1));
    }
    for(auto [x,id]:s){
        ans-=dp[id];
    }
    //for(int i=0;i<m;i++) cout<<i<<" "<<vec[i].x<<" "<<vec[i].y<<' '<<dp[i]<<"\n";
    cout<<ans<<"\n";
}

• Subtask 1: 14 / 14
• Subtask 2: 21 / 21
• Subtask 3: 65 / 65