제출 #261135

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
261135		doowey	별자리 3 (JOI20_constellation3)	C++14	100 / 100	718 ms	72424 KiB

constellation3

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair<ll, ll> pii;

#define fi first
#define se second
#define mp make_pair
#define fastIO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const int N = (int)2e5 + 10;

int A[N];
int L[N];
int R[N];
int C[N];
int X[N];
int Y[N];

vector<int> id[N];

map<pii, vector<pii>> cont;
vector<pii> ele[N];

bool comp(pii a, pii b){
    return a.se - a.fi < b.se - b.fi;
}

vector<int> F[N];
int ld[N], rd[N];
int tin[N];
int tout[N];
int ti;

set<int> sg;
int stin[N];


void dfs(int u){
    tin[u]=++ti;
    for(auto x : F[u]){
        dfs(x);
    }
    auto it = sg.lower_bound(ld[u]);
    while(it != sg.end() && (*it) <= rd[u]){
        stin[(*it)] = tin[u];
        it=sg.erase(it);
    }
    tout[u]=ti;
}

ll dp[N];

struct Node{
    ll val;
    ll lazy;
};

Node T[N * 4 + 512];

void push(int node, int cl, int cr){
    T[node].val += T[node].lazy;
    if(cl != cr){
        T[node * 2].lazy += T[node].lazy;
        T[node * 2 + 1].lazy += T[node].lazy;
    }
    T[node].lazy = 0;
}

void upd(int node, int cl, int cr, int tl, int tr, ll x){
    push(node, cl, cr);
    if(cr < tl || cl > tr)
        return;
    if(cl >= tl && cr <= tr){
        T[node].lazy = x;
        push(node, cl, cr);
        return;
    }
    int mid = (cl + cr) / 2;
    upd(node * 2, cl, mid, tl, tr, x);
    upd(node * 2 + 1, mid + 1, cr, tl, tr, x);
}

ll get(int node, int cl, int cr, int pos){
    push(node, cl, cr);
    if(cl == cr)
        return T[node].val;
    int mid = (cl + cr) / 2;
    if(mid >= pos)
        return get(node * 2, cl, mid, pos);
    else
        return get(node * 2 + 1, mid + 1, cr, pos);
}

void dfs1(int u){
    dp[u]=0;
    for(auto x : F[u]){
        dfs1(x);
        dp[u] += dp[x];
    }
    for(auto x : F[u]){
        upd(1, 1, ti, tin[u], tout[u], dp[x]);
        upd(1, 1, ti, tin[x], tout[x], -dp[x]);
    }
    for(auto x : ele[u]){
        dp[u]=max(dp[u], x.fi + get(1, 1, ti, stin[x.se]));
    }
}

int main(){
    fastIO;
    int n;
    cin >> n;
    A[0]=A[n+1]=(int)1e9 + 100;
    for(int i = 1; i <= n ; i ++ )
        cin >> A[i];
    int q;
    cin >> q;
    ll res = 0;
    for(int i = 1; i <= q; i ++ ){
        cin >> X[i] >> Y[i] >> C[i];
        res += C[i];
        id[X[i]].push_back(i);
    }
    vector<int> ids;
    ids.push_back(0);
    int sz;
    int nx;
    for(int i = 1; i <= n; i ++ ){
        while(A[ids.back()] <= A[i]){
            ids.pop_back();
        }
        ids.push_back(i);
        for(auto p : id[i]){
            sz = ids.size();
            for(int lg = 19; lg >= 0; lg -- ){
                nx = (sz - (1 << lg));
                if(nx < 0) continue;
                if(A[ids[nx]] < Y[p]){
                    sz = nx;
                }
            }
            L[p] = ids[sz-1]+1;
        }
    }
    ids.clear();
    ids.push_back(n + 1);
    for(int i = n ; i >= 1; i -- ){
        while(A[ids.back()] <= A[i]){
            ids.pop_back();
        }
        ids.push_back(i);
        for(auto p : id[i]){
            sz = ids.size();
            for(int lg = 19; lg >= 0; lg -- ){
                nx = (sz - (1 << lg));
                if(nx < 0) continue;
                if(A[ids[nx]] < Y[p]){
                    sz = nx;
                }
            }
            R[p] = ids[sz-1]-1;
        }
    }
    vector<pii> segs;
    for(int i = 1; i <= q; i ++ ){
        if(!cont.count(mp(L[i], R[i]))){
            segs.push_back(mp(L[i], R[i]));
        }
        cont[mp(L[i], R[i])].push_back(mp(C[i], X[i]));
    }
    sort(segs.begin(), segs.end(), comp);
    set<pii> ccd;
    int id;
    for(auto v : segs){
        auto it = ccd.lower_bound(mp(v.fi, -1));
        while(it != ccd.end() && it->fi <= v.se){
            F[id].push_back(it->se);
            it=ccd.erase(it);
        }
        ele[id] = cont[mp(v.fi, v.se)];
        ld[id] = v.fi;
        rd[id] = v.se;
        ccd.insert(mp(v.fi, id));
        id ++ ;
    }
    ld[id]=1;
    rd[id]=n;
    for(auto x : ccd){
        F[id].push_back(x.se);
    }
    for(int i = 1; i <= n; i ++ ){
        sg.insert(i);
    }
    dfs(id);
    dfs1(id);
    cout << res - dp[id] << "\n";
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

constellation3.cpp: In function 'int main()':
constellation3.cpp:176:9: warning: 'id' may be used uninitialized in this function [-Wmaybe-uninitialized]
     int id;
         ^~

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