oj.uz

Submission #1050077

# Submission time Handle Problem Language Result Execution time Memory
1050077 2024-08-09T07:15:05 Z 변재우(#11050) Constellation 3 (JOI20_constellation3) C++17
0 / 100
 4 ms 31468 KB 
#include <bits/stdc++.h>
#define int long long
using namespace std;


const int Nmax=200010;
int N, M, K, all, G[Nmax], A[Nmax], L[Nmax], R[Nmax], Lo[Nmax], Hi[Nmax], D[Nmax], E[Nmax], S[Nmax], P[Nmax];
vector<pair<int, int>> T[Nmax], TT[Nmax], tV, X[Nmax];
vector<int> adj[Nmax];
stack<pair<int, int>> Stk;

int Find(int x) {return G[x]?(G[x]=Find(G[x])):x;}
void Union(int u, int v) {
    u=Find(u), v=Find(v);
    if(u!=v) G[u]=v;
}

set<pair<pair<int, int>, int>> DFS1(int curr) {
    set<pair<pair<int, int>, int>> ret;
    for(auto x:T[curr]) ret.insert({{x.first, curr}, x.second});
    for(int next:adj[curr]) {
        P[next]=curr;
        auto tmp=DFS1(next);
        if(ret.size()<tmp.size()) swap(ret, tmp);
        for(auto x:tmp) ret.insert(x);
    }
    while(true) {
        auto p=ret.lower_bound(make_pair(make_pair(Lo[curr], 0ll), 0ll));
        if(p!=ret.end() && (*p).first.first<=Hi[curr]) X[curr].push_back({(*p).first.second, (*p).second}), ret.erase(p);
        else break;
    }
    return ret;
}

void DFS(int curr) {
    for(int next:adj[curr]) DFS(next), D[curr]+=D[next];
    S[curr]=D[curr];
    for(int next:adj[curr]) E[next]=D[curr]-D[next];
    for(auto [x, v]:X[curr]) {
        int tmp=0;
        tmp+=S[Find(x)];
        for(int i=Find(x); i!=curr; i=P[i]) tmp+=E[i];
        D[curr]=max(D[curr], tmp+v);
    }
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>N;
    for(int i=1; i<=N; i++) cin>>A[i], A[i]=N-A[i]+1;
    cin>>M;
    for(int i=1; i<=M; i++) {
        int x, y, v; cin>>x>>y>>v;
        y=N-y+2, all+=v;
        TT[x].push_back({y, v});
    }
    Stk.push({0, 0});
    for(int i=1; i<=N; i++) {
        while(Stk.top().first>=A[i]) Stk.pop();
        L[i]=Stk.top().second;
        Stk.push({A[i], i});
    }
    while(!Stk.empty()) Stk.pop();
    Stk.push({0, N+1});
    for(int i=N; i>=1; i--) {
        while(Stk.top().first>=A[i]) Stk.pop();
        R[i]=Stk.top().second;
        Stk.push({A[i], i});
    }
    for(int i=1; i<=N; i++) if(A[L[i]]==A[R[i]] && A[L[i]]) Union(L[i], R[i]);
    for(int i=1; i<=N; i++) if(i==Find(i)) {
        Lo[i]=max(A[L[i]], A[R[i]])+1, Hi[i]=A[i];
        tV.push_back({A[i], i});
    }
    sort(tV.begin(), tV.end());
    for(auto [h, k]:tV) {
        if(A[L[k]]==0 && A[R[k]]==0) adj[N+1].push_back(k);
        else if(A[L[k]]>A[R[k]]) adj[Find(L[k])].push_back(k);
        else adj[Find(R[k])].push_back(k);
    }
    for(int i=1; i<=N; i++) for(auto x:TT[i]) T[Find(i)].push_back(x);
    DFS1(N+1);
    DFS(N+1);
    cout<<all-D[N+1];
    return 0;
}

Subtask #1
0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31324 KB Output is correct
2 Correct 3 ms 31464 KB Output is correct
3 Correct 3 ms 31324 KB Output is correct
4 Correct 4 ms 31324 KB Output is correct
5 Incorrect 4 ms 31468 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #2
0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31324 KB Output is correct
2 Correct 3 ms 31464 KB Output is correct
3 Correct 3 ms 31324 KB Output is correct
4 Correct 4 ms 31324 KB Output is correct
5 Incorrect 4 ms 31468 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31324 KB Output is correct
2 Correct 3 ms 31464 KB Output is correct
3 Correct 3 ms 31324 KB Output is correct
4 Correct 4 ms 31324 KB Output is correct
5 Incorrect 4 ms 31468 KB Output isn't correct
6 Halted 0 ms 0 KB -