Submission #249667

#	Time	Username	Problem	Language	Result	Execution time	Memory
249667		egekabas	Constellation 3 (JOI20_constellation3)	C++14	0 / 100	4 ms	5120 KiB

constellation3

#include <bits/stdc++.h>
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<int, int> pii;
typedef pair<ld, ld> pld;
int n, m;
int a[200009];
vector<pii> b[200009];
int dp[200009];
int tot;
int seg[800009];
void build(int v, int tl, int tr){
    if(tl == tr){
        seg[v] = a[tl];
        return;
    }
    build(2*v, tl, (tl+tr)/2);
    build(2*v+1, (tl+tr)/2+1, tr);
    seg[v] = max(seg[2*v], seg[2*v+1]);
}
int get(int v, int tl, int tr, int val){
    if(seg[v] < val) return n;
    if(tl == tr) return tl;
    if(seg[2*v+1] < val)
        return get(2*v, tl, (tl+tr)/2, val);
    return get(2*v+1, (tl+tr)/2+1, tr, val);
}
void erase(int v, int tl, int tr, int idx){
    if(tl == tr){
        seg[v] = -1;
        return;
    }
    if(idx <= (tl+tr)/2)
        erase(2*v, tl, (tl+tr)/2, idx);
    else
        erase(2*v+1, (tl+tr)/2+1, tr, idx);
    seg[v] = max(seg[2*v], seg[2*v+1]);
}
int extra[200009];
int main() {
    
    //freopen("in.txt", "r", stdin);
    //freopen("out.txt", "w", stdout);

    cin >> n;
    for(int i = 0; i < n; ++i)
        cin >> a[i];
    cin >> m;
    while(m--){
        int x, y, c;
        cin >> x >> y >> c;
        b[x-1].pb({y, c});
        tot += c;
    }
    build(1, 0, n-1);
    deque<pii> v = {{1e9+9, n}};
    for(int i = n-1; i >= 0; --i){
        erase(1, 0, n-1, i);
        extra[i] = max(extra[i], extra[i+1]);
        dp[i] = dp[i+1];
        for(auto u : b[i]){
            int bef = get(1, 0, n-1, u.ff);
            if(bef < i)
                extra[bef] = max(extra[bef], extra[i]+u.ss);
            int idx = (*lower_bound(v.begin(), v.end(), mp(u.ff, 0))).ss;
            dp[i] = max(dp[i], u.ss+dp[idx]+extra[i]-extra[idx]);
        }
        while(v[0].ff <= a[i])
            v.pop_front();
        v.push_front({a[i], i});
    }
    cout << tot-dp[0] << '\n';
}   

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