제출 #218984

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
218984		nvmdava	별자리 3 (JOI20_constellation3)	C++17	100 / 100	290 ms	56680 KiB

constellation3

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ff first
#define ss second
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
#define N 200005
#define INF 0x3f3f3f3f
#define MOD 1000000007LL

int a[N];
int l[N], r[N];
vector<pair<int, int> > st[N], tmp;

map<int, ll> ans[N];
ll c[N];

ll res = 0;

void insert(int v, int y, ll s){
    if((--ans[v].upper_bound(y)) -> ss >= s) return;
    ans[v][y] = s;
    auto it = ans[v].upper_bound(y);
    while(it != ans[v].end() && it -> ss <= s)
        it = ans[v].erase(it);
}

void dfs(int v){
    int l = ::l[v];
    int r = ::r[v];
    if(l)
        dfs(l);
    if(r)
        dfs(r);

    ll L, R;

    auto it = --ans[l].upper_bound(a[v]);
    while(ans[l].begin() != it)
        ans[l].erase(ans[l].begin());
    L = c[l] + it -> ss;
    it = --ans[r].upper_bound(a[v]);
    while(ans[r].begin() != it)
        ans[r].erase(ans[r].begin());
    R = c[r] + it -> ss;
    c[l] += R;
    c[r] += L;

    if(ans[l].size() > ans[r].size())
        swap(l, r);

    swap(ans[r], ans[v]);
    swap(c[r], c[v]);

    if(!l)
        c[0] = 0;
    else
        for(auto& x : ans[l])
            insert(v, x.ff, x.ss + c[l] - c[v]);
    for(auto& x : st[v])
        insert(v, x.ff, x.ss + L + R - c[v]);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n;
    cin>>n;
    ans[0][1] = 0;
    for(int i = 1; i <= n; ++i){
        ans[i][1] = 0;
        cin>>a[i];
        while(!tmp.empty() && tmp.back().ff < a[i]){
            l[i] = tmp.back().ss;
            tmp.pop_back();
        }
        if(!tmp.empty())
            r[tmp.back().ss] = i;
        tmp.push_back({a[i], i});
    }

    int q;
    cin>>q;
    while(q--){
        int x, y, s;
        cin>>x>>y>>s;
        res += s;
        st[x].push_back({y, s});
    }

    dfs(tmp[0].ss);

    res -= c[tmp[0].ss] + (--ans[tmp[0].ss].end()) -> ss;

    cout<<res;
}

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