Submission #242054

#	Time	Username	Problem	Language	Result	Execution time	Memory
242054		mhy908	Constellation 3 (JOI20_constellation3)	C++14	100 / 100	555 ms	64940 KiB

constellation3

#include <bits/stdc++.h>
#define eb emplace_back
#define mp make_pair
#define F first
#define S second
using namespace std;
typedef long long LL;
typedef pair<int, int> pii;
typedef pair<int, LL> pil;

struct FENWICK{
    LL tree[200010];
    LL sum(int i){
        LL ans=0;
        while(i){
            ans+=tree[i];
            i-=(i&-i);
        }
        return ans;
    }
    void update(int i, LL num){
        while(i<=200000){
            tree[i]+=num;
            i+=(i&-i);
        }
    }
}fen;
pii tree[800010];
pii f(pii a, pii b){
    pii ret;
    ret.F=max(a.F, b.F);
    if(a.F==ret.F)ret.S=a.S;
    else ret.S=b.S;
    return ret;
}
void update(int point, int s, int e, int num, int val){
    if(s==e){
        tree[point]=mp(val, s);
        return;
    }
    if(num<=(s+e)/2)update(point*2, s, (s+e)/2, num, val);
    else update(point*2+1, (s+e)/2+1, e, num, val);
    tree[point]=f(tree[point*2], tree[point*2+1]);
}
pii query(int point, int s, int e, int a, int b){
    if(a<=s&&e<=b)return tree[point];
    if(e<a||s>b)return mp(-1, 0);
    return f(query(point*2, s, (s+e)/2, a, b), query(point*2+1, (s+e)/2+1, e, a, b));
}
int n, m, re;
vector<pil> arr[200010];
LL dp[400010], sum[400010];
vector<pair<pii, LL> > vc[400010];
set<pair<pii, LL> > s;

int dfs(int l, int r, int t){
    if(l>r)return 0;
    pii tmp=query(1, 1, n, l, r);
    int le=dfs(l, tmp.S-1, tmp.F);
    for(auto i:arr[tmp.S])s.insert(mp(mp(i.F, tmp.S), i.S));
    int ri=dfs(tmp.S+1, r, tmp.F);
    fen.update(l, sum[le]+dp[ri]);
    fen.update(tmp.S, -sum[le]+dp[le]);
    fen.update(tmp.S+1, sum[ri]-dp[ri]);
    fen.update(r+1, -dp[le]-sum[ri]);
    ++re;
    auto it=s.begin();
    while(it!=s.end()){
        auto tmp=*it;
        if(tmp.F.F>t)break;
        vc[re].eb(tmp);
        sum[re]+=tmp.S;
        it++;
    }
    for(auto i:vc[re])s.erase(i);
    dp[re]=sum[re]+dp[le]+dp[ri];
    for(auto i:vc[re])dp[re]=min(dp[re], sum[re]-i.S+fen.sum(i.F.S));
    return re;
}

int main(){
    scanf("%d", &n);
    for(int i=1; i<=n; i++){
        int x;
        scanf("%d", &x);
        update(1, 1, n, i, x);
    }
    scanf("%d", &m);
    for(int i=1; i<=m; i++){
        int x, y, c;
        scanf("%d %d %d", &x, &y, &c);
        arr[x].eb(y, (LL)c);
    }
    dfs(1, n, n+1);
    printf("%lld", dp[re]);
}

Compilation message (stderr)

constellation3.cpp: In function 'int main()':
constellation3.cpp:82:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
constellation3.cpp:85:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &x);
         ~~~~~^~~~~~~~~~
constellation3.cpp:88:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &m);
     ~~~~~^~~~~~~~~~
constellation3.cpp:91:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &x, &y, &c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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