oj.uz

Submission #1119149

# Submission time Handle Problem Language Result Execution time Memory
1119149 2024-11-26T16:34:38 Z ttamx Constellation 3 (JOI20_constellation3) C++17
35 / 100
 143 ms 57488 KB 
#include<bits/stdc++.h>

using namespace std;

using ll = long long;

const int N=2e5+5;
const int K=1<<19;

int n,m;
int a[N];
set<tuple<int,int,int>> star[N];
ll sum;

struct MaxSegtree{
    pair<int,int> t[N];
    void build(int l,int r,int i){
        if(l==r)return void(t[i]={a[l],l});
        int m=(l+r)/2;
        build(l,m,i*2);
        build(m+1,r,i*2+1);
        t[i]=max(t[i*2],t[i*2+1]);
    }
    void build(){
        build(1,n,1);
    }
    pair<int,int> query(int l,int r,int i,int x,int y){
        if(y<l||r<x)return {0,0};
        if(x<=l&&r<=y)return t[i];
        int m=(l+r)/2;
        return max(query(l,m,i*2,x,y),query(m+1,r,i*2+1,x,y));
    }
    pair<int,int> query(int x,int y){
        return query(1,n,1,x,y);
    }
}smx;

struct LazySegtree{
    ll t[K],lz[K];
    void push(int l,int r,int i){
        t[i]+=lz[i];
        if(l<r){
            lz[i*2]+=lz[i];
            lz[i*2+1]+=lz[i];
        }
        lz[i]=0;
    }
    void update(int l,int r,int i,int x,int y,ll v){
        push(l,r,i);
        if(y<l||r<x)return;
        if(x<=l&&r<=y)return lz[i]=v,push(l,r,i);
        int m=(l+r)/2;
        update(l,m,i*2,x,y,v);
        update(m+1,r,i*2+1,x,y,v);
        t[i]=max(t[i*2],t[i*2+1]);
    }
    void update(int x,int y,ll v){
        update(1,n,1,x,y,v);
    }
    ll query(int l,int r,int i,int x,int y){
        push(l,r,i);
        if(y<l||r<x)return 0LL;
        if(x<=l&&r<=y)return t[i];
        int m=(l+r)/2;
        return max(query(l,m,i*2,x,y),query(m+1,r,i*2+1,x,y));
    }
    ll query(int x,int y){
        return query(1,n,1,x,y);
    }
}seg;

void merge(set<tuple<int,int,int>> &a,set<tuple<int,int,int>> &b){
    if(a.size()<b.size())swap(a,b);
    for(auto &e:b)a.emplace(e);
    b.clear();
}

pair<ll,int> solve(int l,int r,int h){
    auto [hh,mid]=smx.query(l,r);
    auto &s=star[mid];
    ll lmx=0,rmx=0;
    if(l<mid){
        auto [mx,id]=solve(l,mid-1,hh);
        merge(s,star[id]);
        lmx=mx;
    }
    if(mid<r){
        auto [mx,id]=solve(mid+1,r,hh);
        merge(s,star[id]);
        rmx=mx;
    }
    seg.update(l,mid,rmx);
    seg.update(mid,r,lmx);
    ll res=seg.query(l,r);
    for(auto it=s.begin();it!=s.end()&&get<0>(*it)<=h;it=s.erase(it)){
        auto [y,x,c]=*it;
        res=max(res,seg.query(x,x)+c);
    }
    return {res,mid};
}

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> n;
    for(int i=1;i<=n;i++){
        cin >> a[i];
    }
    cin >> m;
    for(int i=1;i<=m;i++){
        int x,y,c;
        cin >> x >> y >> c;
        star[x].emplace(y,x,c);
        sum+=c;
    }
    smx.build();
    cout << sum-solve(1,n,n).first;
}

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13136 KB Output is correct
2 Correct 3 ms 13136 KB Output is correct
3 Correct 3 ms 13252 KB Output is correct
4 Correct 3 ms 13148 KB Output is correct
5 Correct 3 ms 13136 KB Output is correct
6 Correct 3 ms 13236 KB Output is correct
7 Correct 3 ms 13136 KB Output is correct
8 Correct 3 ms 13136 KB Output is correct
9 Correct 3 ms 13136 KB Output is correct
10 Correct 3 ms 13136 KB Output is correct
11 Correct 3 ms 13136 KB Output is correct
12 Correct 4 ms 13136 KB Output is correct
13 Correct 3 ms 13208 KB Output is correct
14 Correct 4 ms 13136 KB Output is correct
15 Correct 4 ms 13136 KB Output is correct
16 Correct 4 ms 13392 KB Output is correct
17 Correct 4 ms 13136 KB Output is correct
18 Correct 3 ms 13392 KB Output is correct
19 Correct 4 ms 13136 KB Output is correct
20 Correct 3 ms 13136 KB Output is correct
21 Correct 3 ms 13392 KB Output is correct
22 Correct 4 ms 13136 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13136 KB Output is correct
2 Correct 3 ms 13136 KB Output is correct
3 Correct 3 ms 13252 KB Output is correct
4 Correct 3 ms 13148 KB Output is correct
5 Correct 3 ms 13136 KB Output is correct
6 Correct 3 ms 13236 KB Output is correct
7 Correct 3 ms 13136 KB Output is correct
8 Correct 3 ms 13136 KB Output is correct
9 Correct 3 ms 13136 KB Output is correct
10 Correct 3 ms 13136 KB Output is correct
11 Correct 3 ms 13136 KB Output is correct
12 Correct 4 ms 13136 KB Output is correct
13 Correct 3 ms 13208 KB Output is correct
14 Correct 4 ms 13136 KB Output is correct
15 Correct 4 ms 13136 KB Output is correct
16 Correct 4 ms 13392 KB Output is correct
17 Correct 4 ms 13136 KB Output is correct
18 Correct 3 ms 13392 KB Output is correct
19 Correct 4 ms 13136 KB Output is correct
20 Correct 3 ms 13136 KB Output is correct
21 Correct 3 ms 13392 KB Output is correct
22 Correct 4 ms 13136 KB Output is correct
23 Correct 4 ms 13392 KB Output is correct
24 Correct 5 ms 13392 KB Output is correct
25 Correct 6 ms 13392 KB Output is correct
26 Correct 6 ms 13408 KB Output is correct
27 Correct 4 ms 13392 KB Output is correct
28 Correct 5 ms 13392 KB Output is correct
29 Correct 6 ms 13392 KB Output is correct
30 Correct 6 ms 13316 KB Output is correct
31 Correct 7 ms 13392 KB Output is correct
32 Correct 5 ms 13648 KB Output is correct
33 Correct 6 ms 13648 KB Output is correct
34 Correct 5 ms 13392 KB Output is correct
35 Correct 5 ms 13392 KB Output is correct
36 Correct 6 ms 13700 KB Output is correct
37 Correct 7 ms 13648 KB Output is correct
38 Correct 4 ms 13648 KB Output is correct
39 Correct 5 ms 13392 KB Output is correct
40 Correct 6 ms 13648 KB Output is correct
41 Correct 7 ms 13392 KB Output is correct
42 Correct 6 ms 13392 KB Output is correct
43 Correct 8 ms 13604 KB Output is correct
44 Correct 5 ms 13392 KB Output is correct

Subtask #3
0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 13136 KB Output is correct
2 Correct 3 ms 13136 KB Output is correct
3 Correct 3 ms 13252 KB Output is correct
4 Correct 3 ms 13148 KB Output is correct
5 Correct 3 ms 13136 KB Output is correct
6 Correct 3 ms 13236 KB Output is correct
7 Correct 3 ms 13136 KB Output is correct
8 Correct 3 ms 13136 KB Output is correct
9 Correct 3 ms 13136 KB Output is correct
10 Correct 3 ms 13136 KB Output is correct
11 Correct 3 ms 13136 KB Output is correct
12 Correct 4 ms 13136 KB Output is correct
13 Correct 3 ms 13208 KB Output is correct
14 Correct 4 ms 13136 KB Output is correct
15 Correct 4 ms 13136 KB Output is correct
16 Correct 4 ms 13392 KB Output is correct
17 Correct 4 ms 13136 KB Output is correct
18 Correct 3 ms 13392 KB Output is correct
19 Correct 4 ms 13136 KB Output is correct
20 Correct 3 ms 13136 KB Output is correct
21 Correct 3 ms 13392 KB Output is correct
22 Correct 4 ms 13136 KB Output is correct
23 Correct 4 ms 13392 KB Output is correct
24 Correct 5 ms 13392 KB Output is correct
25 Correct 6 ms 13392 KB Output is correct
26 Correct 6 ms 13408 KB Output is correct
27 Correct 4 ms 13392 KB Output is correct
28 Correct 5 ms 13392 KB Output is correct
29 Correct 6 ms 13392 KB Output is correct
30 Correct 6 ms 13316 KB Output is correct
31 Correct 7 ms 13392 KB Output is correct
32 Correct 5 ms 13648 KB Output is correct
33 Correct 6 ms 13648 KB Output is correct
34 Correct 5 ms 13392 KB Output is correct
35 Correct 5 ms 13392 KB Output is correct
36 Correct 6 ms 13700 KB Output is correct
37 Correct 7 ms 13648 KB Output is correct
38 Correct 4 ms 13648 KB Output is correct
39 Correct 5 ms 13392 KB Output is correct
40 Correct 6 ms 13648 KB Output is correct
41 Correct 7 ms 13392 KB Output is correct
42 Correct 6 ms 13392 KB Output is correct
43 Correct 8 ms 13604 KB Output is correct
44 Correct 5 ms 13392 KB Output is correct
45 Runtime error 143 ms 57488 KB Execution killed with signal 11
46 Halted 0 ms 0 KB -