제출 #999512

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
999512		snpmrnhlol	별자리 3 (JOI20_constellation3)	C++17	35 / 100	1506 ms	155732 KiB

constellation3

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N = 2e5;
const ll G = 2*N;
const ll logN = 20;
ll n,m;
vector <ll> e[G];
ll v[N];
vector <ll> lefte[N + 1];
vector <ll> righte[N + 1];
ll prleft[N + 1][logN],prright[N + 1][logN];
ll subleft[N + 1],subright[N + 1];
ll leftside[N + 1],rightside[N + 1];
///bear your fangs its time to fight
///pa pa pa parade in shame tonight
ll ordleft[N + 1],ordright[N + 1];
ll ord2left[N + 1],ord2right[N + 1];
ll cntleft = 0,cntright = 0;
ll leftid[N],rightid[N];
ll fenleft[N + 1],fenright[N + 1];
///
ll stk[N];
vector <ll> p;
struct star{
    ll x,y,c;
}v2[N];
vector <ll> cand[G];
map<ll,pair<ll,ll>> f;
vector <ll> points;
ll dp[G];
ll fuckleft[N],fuckright[N];
ll cnt = 0;
void addedge(ll u,ll w){
    e[u].push_back(w);
}
void addleft(ll pos,ll nr){
    for(ll i = pos;i <= n;i|=(i + 1)){
        fenleft[i]+=nr;
    }
}
void addright(ll pos,ll nr){
    for(ll i = pos;i <= n;i|=(i + 1)){
        fenright[i]+=nr;
    }
}
ll getleft(ll pos){
    ll r = 0;
    for(ll i = pos;i >= 0;i&=(i + 1),i--){
        r+=fenleft[i];
    }
    return r;
}
ll getright(ll pos){
    ll r = 0;
    for(ll i = pos;i >= 0;i&=(i + 1),i--){
        r+=fenright[i];
    }
    return r;
}
void dfs(ll node){
    ll mx = 0;
    for(auto i:e[node]){
        dfs(i);
        mx+=dp[i];
    }
    for(auto i:cand[node]){
        ///leftadd
        star s = v2[i];
        ll candcost = s.c;

        ll j = s.x;
        candcost+=getright(ordright[j]);
        while(j != n && v[j] < s.y){j = rightside[j];};
        candcost-=getright(ordright[j]);
        j = s.x;
        candcost+=getleft(ordleft[j]);
        while(j != n && v[j] < s.y){j = leftside[j];};
        candcost-=getleft(ordleft[j]);
        mx = max(mx,candcost);
    }
    dp[node] = mx;
    if(ord2left[node] != -1){
        fuckleft[ord2left[node]]+=dp[node];
        addleft(ordleft[ord2left[node]],dp[node]);
        addleft(ordleft[ord2left[node]] + subleft[ord2left[node]],-dp[node]);
    }
    if(ord2right[node] != -1){
        fuckright[ord2right[node]]+=dp[node];
        addright(ordright[ord2right[node]],dp[node]);
        addright(ordright[ord2right[node]] + subright[ord2right[node]],-dp[node]);
    }
}
void dfsleft(ll node, ll p){
    prleft[node][0] = p;
    subleft[node] = 1;
    ordleft[node] = cntleft++;
    for(auto i:lefte[node]){
        dfsleft(i, node);
        subleft[node]+=subleft[i];
    }
}
void dfsright(ll node, ll p){
    prright[node][0] = p;
    subright[node] = 1;
    ordright[node] = cntright++;
    for(auto i:righte[node]){
        dfsright(i, node);
        subright[node]+=subright[i];
    }
}
int main(){
    cin>>n;
    p.resize(n);
    for(ll i = 0;i < n;i++){
        cin>>v[i];
        p[i] = i;
        leftid[i] = rightid[i] = -1;
    }
    sort(p.begin(),p.end(),[&](ll a,ll b){
        if(v[a] == v[b])return a < b;
        return v[a] > v[b];
    });
    cin>>m;
    ll sum = 0;
    for(ll i = 0;i < m;i++){
        cin>>v2[i].x>>v2[i].y>>v2[i].c;
        sum+=v2[i].c;
        v2[i].x--;
    }
    sort(v2,v2 + m,[&](star a,star b){
         return a.y > b.y;
    });
    f[0] = {n - 1,cnt++};
    ll pt = 0;
    ll pt2 = 0;
    for(ll i = n;i >= 1;i--){
        points.clear();
        while(pt2 < n && v[p[pt2]] >= i){
            points.push_back(p[pt2]);
            pt2++;
        }
        ll j = 0;
        while(j < points.size()){
            auto it = prev(f.upper_bound(points[j]));
            ll k = j;
            while(k < points.size() && points[k] <= it->second.first){
                k++;
            }
            ll l = it->first;
            ll r = it->second.first;
            ll id = it->second.second;
            f.erase(it);
            for(ll p = j;p <= k;p++){
                ll lside = (p == j?l:points[p - 1] + 1);
                ll rside = (p == k?r:points[p] - 1);
                if(lside <= rside){
                    addedge(id,cnt);
                    f[lside] = {rside,cnt};
                    ord2left[cnt] = ord2right[cnt] = -1;
                    if(p != k){
                        leftid[rside + 1] = cnt;
                        ord2left[cnt] = rside + 1;
                    }
                    if(p != j){
                        rightid[lside - 1] = cnt;
                        ord2right[cnt] = lside - 1;
                    }
                    cnt++;
                }
            }
            j = k;
        }
        while(pt < m && v2[pt].y >= i){
            ll id = prev(f.upper_bound(v2[pt].x))->second.second;
            cand[id].push_back(pt);
            pt++;
        }
    }
    ll cnt2 = 0;
    for(ll i = 0;i < n;i++){
        while(cnt2 > 0 && v[i] > v[stk[cnt2 - 1]]){
            cnt2--;
        }
        leftside[i] = (cnt2 == 0?n:stk[cnt2 - 1]);
        lefte[leftside[i]].push_back(i);
        stk[cnt2++] = i;
    }
    cnt2 = 0;
    for(ll i = n - 1;i >= 0;i--){
        while(cnt2 > 0 && v[i] > v[stk[cnt2 - 1]]){
            cnt2--;
        }
        rightside[i] = (cnt2 == 0?n:stk[cnt2 - 1]);
        righte[rightside[i]].push_back(i);
        stk[cnt2++] = i;
    }
    dfsleft(n, -1);
    dfsright(n, -1);
    for(ll j = 1;j < logN;j++){
        for(ll i = 0;i <= n;i++){
            prleft[i][j] = prleft[prleft[i][j - 1]][j - 1];
            prright[i][j] = prright[prright[i][j - 1]][j - 1];
        }
    }
    dfs(0);
    cout<<sum - dp[0];
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

constellation3.cpp: In function 'int main()':
constellation3.cpp:144:17: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  144 |         while(j < points.size()){
      |               ~~^~~~~~~~~~~~~~~
constellation3.cpp:147:21: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  147 |             while(k < points.size() && points[k] <= it->second.first){
      |                   ~~^~~~~~~~~~~~~~~

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