Submission #1005392

#	Time	Username	Problem	Language	Result	Execution time	Memory
1005392		Unforgettablepl	Constellation 3 (JOI20_constellation3)	C++17	0 / 100	1564 ms	49820 KiB

constellation3

// #pragma GCC optimize("O3")
#include <bits/stdc++.h>
using namespace std;

#define int long long

struct segtree{
    vector<pair<int,int>> tree;
    segtree():tree(524288){}
    void update(int k,int x){
        k+=262144;
        tree[k] = {x,k-262144};
        while(k/=2){
            tree[k]=max(tree[2*k],tree[2*k+1]);
        }
    }
    int get(int l,int r){
        l+=262144;r+=262144;
        pair<int,int> ans = {0,0};
        while(l<=r){
            if(l&1)ans=max(ans,tree[l++]);
            if(r%2==0)ans=max(ans,tree[r--]);
            l/=2;r/=2;
        }
        return ans.second;
    }
};

pair<int,int> adj[200001];
int tree[200001];
vector<pair<int,int>> chains[200001];
int arr[200001];
int stidx[200001];
int lift[18][200001];
int idx[200001];
int DP[200001];
segtree seg;
int c;

void place(int x,int y,int c){
    int node = idx[x];
    for(int bit=17;bit>=0;bit--){
        if(tree[lift[bit][node]]<y)node = lift[bit][node];
    }
    chains[node].emplace_back(x,c);
}

void build(int x,int l,int r){
    int mid = seg.get(l,r);
    idx[mid] = x;
    tree[x] = arr[mid];
    stidx[x] = mid;
    if(mid!=l){
        adj[x].first = ++c;
        lift[0][c] = x;
        build(c,l,mid-1);
    }
    if(mid!=r){
        adj[x].second = ++c;
        lift[0][c] = x;
        build(c,mid+1,r);
    }
}

void merge(pair<int,map<int,int>> &a,pair<int,map<int,int>> &b){
    if(a.second.size()<b.second.size())swap(a,b);
    int offset = b.first-a.first;
    for(auto[x,y]:b.second){
        a.second[x] = y+offset; 
    }
}

pair<int,map<int,int>> calc(int x){
    pair<int,map<int,int>> curr = {0,{}};
    pair<int,map<int,int>> l = {0,{}},r = {0,{}};
    if(adj[x].first)l=calc(adj[x].first);
    if(adj[x].second)r=calc(adj[x].second);
    l.first+=DP[adj[x].second];
    r.first+=DP[adj[x].first];
    merge(curr,l);
    merge(curr,r);
    if(adj[x].second){
        auto t = calc(adj[x].second);
        t.first+=DP[adj[x].first];
        merge(curr,t);
    }
    DP[x] = DP[adj[x].first]+DP[adj[x].second];
    curr.second[stidx[x]] = DP[x]-curr.first;
    for(auto[a,b]:chains[x]){
        DP[x] = max(DP[x],curr.second[a]+curr.first+b);
    }
    return move(curr);
}

int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    int n;
    cin >> n;
    for(int i=1;i<=n;i++){cin>>arr[i];seg.update(i,arr[i]);}
    build(++c,1,n);
    assert(c==n);
    for(int bit=1;bit<18;bit++){
        for(int i=1;i<=n;i++){
            lift[bit][i] = lift[bit-1][lift[bit-1][i]];
        }
    }
    tree[0] = 1e15;
    int m;
    cin >> m;
    int sum = 0;
    for(int i=1;i<=m;i++){
        int x,y,c;cin>>x>>y>>c;
        place(x,y,c);
        sum+=c;
    }
    calc(1);
    cout << sum-DP[1] << '\n';
}

Compilation message (stderr)

constellation3.cpp: In function 'std::pair<long long int, std::map<long long int, long long int> > calc(long long int)':
constellation3.cpp:92:16: warning: moving a local object in a return statement prevents copy elision [-Wpessimizing-move]
   92 |     return move(curr);
      |            ~~~~^~~~~~
constellation3.cpp:92:16: note: remove 'std::move' call

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