Submission #1112350

#	Time	Username	Problem	Language	Result	Execution time	Memory
1112350		onlk97	Constellation 3 (JOI20_constellation3)	C++14	100 / 100	234 ms	26188 KiB

constellation3

#include <bits/stdc++.h>
#define int long long
#define x first
#define y second
#define pb push_back
using namespace std;
using pii=pair <int,int>;
using tii=pair <pii,int>;
bool cmp(tii a,tii b){
    return a.x.y<b.x.y;
}
int bit[200010];
void upd(int pos,int val){
    for (int i=pos; i<200010; i+=i&(-i)) bit[i]+=val;
}
int qry(int pos){
    int ret=0;
    for (int i=pos; i>0; i-=i&(-i)) ret+=bit[i];
    return ret;
}
signed main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n;
    cin>>n;
    int a[n+1];
    for (int i=1; i<=n; i++) cin>>a[i];
    pii p[n+1];
    for (int i=1; i<=n; i++) p[i]={a[i],i};
    sort(p+1,p+n+1);
    int m;
    cin>>m;
    tii st[m+1];
    for (int i=1; i<=m; i++) cin>>st[i].x.x>>st[i].x.y>>st[i].y;
    sort(st+1,st+m+1,cmp);
    int ans=0,ptr=1;
    set <int> rem;
    for (int i=1; i<=n; i++) rem.insert(i);
    for (int i=1; i<=m; i++){
        while (ptr<=n&&p[ptr].x<st[i].x.y){
            rem.erase(p[ptr].y);
            ptr++;
        }
        int cost=st[i].y-qry(st[i].x.x);
        if (cost>0){
            ans+=cost;
            auto it=rem.lower_bound(st[i].x.x);
            int r=(it==rem.end()?n:(*it)-1);
            int l=(it==rem.begin()?1:*(--it)+1);
            upd(l,cost); upd(r+1,-cost);
        }
    }
    int sum=0;
    for (int i=1; i<=m; i++) sum+=st[i].y;
    cout<<sum-ans<<'\n';
}

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