oj.uz

Submission #1050089

# Submission time Handle Problem Language Result Execution time Memory
1050089 2024-08-09T07:18:06 Z 변재우(#11050) Constellation 3 (JOI20_constellation3) C++17
35 / 100
 1500 ms 94228 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[i]==A[i+1]) Union(i, i+1);
    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
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31324 KB Output is correct
2 Correct 4 ms 31428 KB Output is correct
3 Correct 3 ms 31324 KB Output is correct
4 Correct 4 ms 31324 KB Output is correct
5 Correct 3 ms 31416 KB Output is correct
6 Correct 4 ms 31428 KB Output is correct
7 Correct 4 ms 31324 KB Output is correct
8 Correct 4 ms 31324 KB Output is correct
9 Correct 4 ms 31320 KB Output is correct
10 Correct 4 ms 31392 KB Output is correct
11 Correct 5 ms 31388 KB Output is correct
12 Correct 5 ms 31320 KB Output is correct
13 Correct 4 ms 31428 KB Output is correct
14 Correct 4 ms 31320 KB Output is correct
15 Correct 4 ms 31324 KB Output is correct
16 Correct 5 ms 31544 KB Output is correct
17 Correct 6 ms 31324 KB Output is correct
18 Correct 6 ms 31324 KB Output is correct
19 Correct 4 ms 31324 KB Output is correct
20 Correct 4 ms 31324 KB Output is correct
21 Correct 4 ms 31324 KB Output is correct
22 Correct 3 ms 31324 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31324 KB Output is correct
2 Correct 4 ms 31428 KB Output is correct
3 Correct 3 ms 31324 KB Output is correct
4 Correct 4 ms 31324 KB Output is correct
5 Correct 3 ms 31416 KB Output is correct
6 Correct 4 ms 31428 KB Output is correct
7 Correct 4 ms 31324 KB Output is correct
8 Correct 4 ms 31324 KB Output is correct
9 Correct 4 ms 31320 KB Output is correct
10 Correct 4 ms 31392 KB Output is correct
11 Correct 5 ms 31388 KB Output is correct
12 Correct 5 ms 31320 KB Output is correct
13 Correct 4 ms 31428 KB Output is correct
14 Correct 4 ms 31320 KB Output is correct
15 Correct 4 ms 31324 KB Output is correct
16 Correct 5 ms 31544 KB Output is correct
17 Correct 6 ms 31324 KB Output is correct
18 Correct 6 ms 31324 KB Output is correct
19 Correct 4 ms 31324 KB Output is correct
20 Correct 4 ms 31324 KB Output is correct
21 Correct 4 ms 31324 KB Output is correct
22 Correct 3 ms 31324 KB Output is correct
23 Correct 5 ms 31692 KB Output is correct
24 Correct 4 ms 31580 KB Output is correct
25 Correct 4 ms 31580 KB Output is correct
26 Correct 5 ms 31688 KB Output is correct
27 Correct 4 ms 31580 KB Output is correct
28 Correct 6 ms 31580 KB Output is correct
29 Correct 5 ms 31576 KB Output is correct
30 Correct 6 ms 31660 KB Output is correct
31 Correct 7 ms 31580 KB Output is correct
32 Correct 6 ms 32024 KB Output is correct
33 Correct 6 ms 31832 KB Output is correct
34 Correct 5 ms 31836 KB Output is correct
35 Correct 5 ms 31892 KB Output is correct
36 Correct 6 ms 31580 KB Output is correct
37 Correct 6 ms 31580 KB Output is correct
38 Correct 4 ms 32092 KB Output is correct
39 Correct 5 ms 31580 KB Output is correct
40 Correct 8 ms 31836 KB Output is correct
41 Correct 5 ms 31580 KB Output is correct
42 Correct 6 ms 31580 KB Output is correct
43 Correct 6 ms 31916 KB Output is correct
44 Correct 5 ms 31688 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 31324 KB Output is correct
2 Correct 4 ms 31428 KB Output is correct
3 Correct 3 ms 31324 KB Output is correct
4 Correct 4 ms 31324 KB Output is correct
5 Correct 3 ms 31416 KB Output is correct
6 Correct 4 ms 31428 KB Output is correct
7 Correct 4 ms 31324 KB Output is correct
8 Correct 4 ms 31324 KB Output is correct
9 Correct 4 ms 31320 KB Output is correct
10 Correct 4 ms 31392 KB Output is correct
11 Correct 5 ms 31388 KB Output is correct
12 Correct 5 ms 31320 KB Output is correct
13 Correct 4 ms 31428 KB Output is correct
14 Correct 4 ms 31320 KB Output is correct
15 Correct 4 ms 31324 KB Output is correct
16 Correct 5 ms 31544 KB Output is correct
17 Correct 6 ms 31324 KB Output is correct
18 Correct 6 ms 31324 KB Output is correct
19 Correct 4 ms 31324 KB Output is correct
20 Correct 4 ms 31324 KB Output is correct
21 Correct 4 ms 31324 KB Output is correct
22 Correct 3 ms 31324 KB Output is correct
23 Correct 5 ms 31692 KB Output is correct
24 Correct 4 ms 31580 KB Output is correct
25 Correct 4 ms 31580 KB Output is correct
26 Correct 5 ms 31688 KB Output is correct
27 Correct 4 ms 31580 KB Output is correct
28 Correct 6 ms 31580 KB Output is correct
29 Correct 5 ms 31576 KB Output is correct
30 Correct 6 ms 31660 KB Output is correct
31 Correct 7 ms 31580 KB Output is correct
32 Correct 6 ms 32024 KB Output is correct
33 Correct 6 ms 31832 KB Output is correct
34 Correct 5 ms 31836 KB Output is correct
35 Correct 5 ms 31892 KB Output is correct
36 Correct 6 ms 31580 KB Output is correct
37 Correct 6 ms 31580 KB Output is correct
38 Correct 4 ms 32092 KB Output is correct
39 Correct 5 ms 31580 KB Output is correct
40 Correct 8 ms 31836 KB Output is correct
41 Correct 5 ms 31580 KB Output is correct
42 Correct 6 ms 31580 KB Output is correct
43 Correct 6 ms 31916 KB Output is correct
44 Correct 5 ms 31688 KB Output is correct
45 Correct 160 ms 61620 KB Output is correct
46 Correct 146 ms 61876 KB Output is correct
47 Correct 184 ms 62140 KB Output is correct
48 Correct 189 ms 62136 KB Output is correct
49 Correct 147 ms 61116 KB Output is correct
50 Correct 149 ms 60852 KB Output is correct
51 Correct 146 ms 62312 KB Output is correct
52 Correct 147 ms 62152 KB Output is correct
53 Correct 149 ms 61296 KB Output is correct
54 Execution timed out 1593 ms 94228 KB Time limit exceeded
55 Halted 0 ms 0 KB -