Submission #711990

#	Time	Username	Problem	Language	Result	Execution time	Memory
711990		anton	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	456 ms	56688 KiB

constellation3

#include<bits/stdc++.h>

#define ll long long

using namespace std;

struct Star{
    int x, y;
    ll c;
    Star(){}

    bool operator<(const Star& b) const{
        return y>b.y;
    }
};

struct Node{
    ll dp;
    int anc;
    int l, r;
    vector<int> ch;
    vector<Star> stars;
    Node(int L, int R, int ANC){
        l = L;
        r= R;
        dp =0;
        anc = ANC;
    }
};

vector<int> A;
vector<pair<int, int>> q;
vector<int> waiting;
vector<Node> tree;

vector<vector<Star>> S;  
priority_queue<Star> cur_stars;

const int INF = 1000*1000*1000*2;
const int bar = (1<<18);

struct SNode{
    ll delta;
    SNode(ll d){
        delta =d;
    }
    SNode(){
        delta = 0;
    }
};
vector<SNode> seg_tree(2*bar);

void add(int beg, int fin, ll val){
    if(beg>=fin){
        seg_tree[beg].delta += val;
    }
    else if(beg%2 == 1){
        seg_tree[beg].delta += val;
        add(beg+1, fin, val);
    }
    else if(fin%2== 0){
        seg_tree[fin].delta += val;
        add(beg, fin-1, val);
    }
    else{
        add(beg/2, fin/2, val);
    }
}

ll get(int id){
    //cout<<"get "<<id<<endl;
    id+= bar;
    ll r= 0;
    for(int i = id; i>0; i/=2){
        r+=seg_tree[i].delta;
    }
    //cout<<r<<endl;
    return r;
}

void update_waiting(pair<int, int> prev, int prev_id){
    while(waiting.size()>0 && tree[waiting.back()].l >= prev.first+1){
        auto child = waiting.back();
        waiting.pop_back();
        tree[child].anc = tree.size()-1;
        tree.back().ch.push_back(child);
    }
    waiting.push_back(tree.size() -1);
}
void update_stars(int height, int id){
    while(cur_stars.size()>0 && cur_stars.top().y<= height){
        tree[id].stars.push_back(cur_stars.top());
        //cout<<"star "<<cur_stars.top().y<<" "<<cur_stars.top().c<<endl;
        cur_stars.pop();
    }
}
void add_interval(int i){
    auto prev= q.back();
    //cout<<i<<" "<<prev.first<<" "<<prev.second<<endl;
    if(prev.first < i-1){
        tree.push_back(Node(prev.first+1, i-1, -1));
        update_waiting(prev, tree.size()-1);
        update_stars(min(prev.second, A[i]), tree.size()-1);
    }
}

void DFS(int id){
    ////cout<<"started "<<tree[id].l<<" "<<tree[id].r<<endl;
    ll total= 0;
    for(auto child: tree[id].ch){
        DFS(child);
        total += tree[child].dp;
    }
    
     add(tree[id].l + bar, tree[id].r + bar, total);
    for(auto child: tree[id].ch){
        //cout<<"adding "<<tree[child].l<<" "<<tree[child].r<<total-tree[child].dp<<endl;
        add(tree[child].l + bar, tree[child].r + bar, -tree[child].dp);
    }
    tree[id].dp = total;
    for(auto s: tree[id].stars){
        //cout<<"DFS star "<< s.c<<endl;
        tree[id].dp = max(tree[id].dp, s.c +get(s.x));
    }
    //cout<<"id :"<<tree[id].l<<' '<<tree[id].r<<" "<<total<<' '<<tree[id].dp<<endl;
}

int main(){
    int n;
    cin>>n;
    A.resize(n+2);
    A[0] = INF;
    A[n+1] = INF;



    for(int i= 1; i<=n; i++){
        cin>>A[i];
    }
    int m;
    cin>>m;
    S.resize(n+2);

    ll sum_stars = 0;
    for(int i = 0; i<m; i++){
        Star s = Star();
        cin>>s.x>>s.y>>s.c;
        //cout<<s.x<<" "<<s.y<<" "<<s.c<<endl;
        S[s.x].push_back(s);
        sum_stars += s.c;
    }
    int cur = 0;


    q.push_back(pair<int, int>(0,A[0]));


    for(int i = 1; i<=n+1; i++){
        int cur = A[i];
        while(q.size()>0 && q.back().second<=cur){
            add_interval(i);
            q.pop_back();
        }
        //cout<<q.size()<<endl;
        if(q.size()>0){
            add_interval(i);
        }
        
        q.push_back(pair<int, int>(i, A[i]));
        for(auto star: S[i]){
            cur_stars.push(star);
        }

    }

    int root= tree.size()-1;
    DFS(root);
    cout<<sum_stars -tree[root].dp<<endl;
}

Compilation message (stderr)

constellation3.cpp: In function 'int main()':
constellation3.cpp:152:9: warning: unused variable 'cur' [-Wunused-variable]
  152 |     int cur = 0;
      |         ^~~

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