oj.uz

Submission #999513

# Submission time Handle Problem Language Result Execution time Memory
999513 2024-06-15T16:33:19 Z snpmrnhlol Constellation 3 (JOI20_constellation3) C++17
100 / 100
 566 ms 163176 KB 
#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]);
        for(int k = logN - 1;k >= 0;k--){
            if(v[prright[j][k]] < s.y && prright[j][k] != n){
                j = prright[j][k];
            }
        }
        j = prright[j][0];
        candcost-=getright(ordright[j]);
        j = s.x;
        candcost+=getleft(ordleft[j]);
        for(int k = logN - 1;k >= 0;k--){
            if(v[prleft[j][k]] < s.y && prleft[j][k] != n){
                j = prleft[j][k];
            }
        }
        j = prleft[j][0];
        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, n);
    dfsright(n, n);
    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;
}

Compilation message

constellation3.cpp: In function 'int main()':
constellation3.cpp:154: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]
  154 |         while(j < points.size()){
      |               ~~^~~~~~~~~~~~~~~
constellation3.cpp:157: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]
  157 |             while(k < points.size() && points[k] <= it->second.first){
      |                   ~~^~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 58200 KB Output is correct
2 Correct 9 ms 62300 KB Output is correct
3 Correct 8 ms 62408 KB Output is correct
4 Correct 8 ms 58200 KB Output is correct
5 Correct 8 ms 60256 KB Output is correct
6 Correct 9 ms 62300 KB Output is correct
7 Correct 8 ms 58204 KB Output is correct
8 Correct 9 ms 60252 KB Output is correct
9 Correct 8 ms 60248 KB Output is correct
10 Correct 8 ms 58204 KB Output is correct
11 Correct 10 ms 58204 KB Output is correct
12 Correct 11 ms 58224 KB Output is correct
13 Correct 8 ms 62300 KB Output is correct
14 Correct 9 ms 58204 KB Output is correct
15 Correct 8 ms 60252 KB Output is correct
16 Correct 7 ms 58204 KB Output is correct
17 Correct 8 ms 60252 KB Output is correct
18 Correct 8 ms 60252 KB Output is correct
19 Correct 9 ms 62300 KB Output is correct
20 Correct 8 ms 62348 KB Output is correct
21 Correct 9 ms 62432 KB Output is correct
22 Correct 8 ms 62420 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 58200 KB Output is correct
2 Correct 9 ms 62300 KB Output is correct
3 Correct 8 ms 62408 KB Output is correct
4 Correct 8 ms 58200 KB Output is correct
5 Correct 8 ms 60256 KB Output is correct
6 Correct 9 ms 62300 KB Output is correct
7 Correct 8 ms 58204 KB Output is correct
8 Correct 9 ms 60252 KB Output is correct
9 Correct 8 ms 60248 KB Output is correct
10 Correct 8 ms 58204 KB Output is correct
11 Correct 10 ms 58204 KB Output is correct
12 Correct 11 ms 58224 KB Output is correct
13 Correct 8 ms 62300 KB Output is correct
14 Correct 9 ms 58204 KB Output is correct
15 Correct 8 ms 60252 KB Output is correct
16 Correct 7 ms 58204 KB Output is correct
17 Correct 8 ms 60252 KB Output is correct
18 Correct 8 ms 60252 KB Output is correct
19 Correct 9 ms 62300 KB Output is correct
20 Correct 8 ms 62348 KB Output is correct
21 Correct 9 ms 62432 KB Output is correct
22 Correct 8 ms 62420 KB Output is correct
23 Correct 10 ms 58460 KB Output is correct
24 Correct 12 ms 62516 KB Output is correct
25 Correct 12 ms 58460 KB Output is correct
26 Correct 12 ms 62556 KB Output is correct
27 Correct 12 ms 62556 KB Output is correct
28 Correct 14 ms 62360 KB Output is correct
29 Correct 12 ms 60508 KB Output is correct
30 Correct 11 ms 58488 KB Output is correct
31 Correct 11 ms 62600 KB Output is correct
32 Correct 11 ms 62556 KB Output is correct
33 Correct 11 ms 62556 KB Output is correct
34 Correct 11 ms 58476 KB Output is correct
35 Correct 11 ms 58456 KB Output is correct
36 Correct 11 ms 62556 KB Output is correct
37 Correct 11 ms 62556 KB Output is correct
38 Correct 10 ms 58460 KB Output is correct
39 Correct 13 ms 62556 KB Output is correct
40 Correct 10 ms 60516 KB Output is correct
41 Correct 10 ms 58456 KB Output is correct
42 Correct 13 ms 62552 KB Output is correct
43 Correct 11 ms 62556 KB Output is correct
44 Correct 11 ms 62556 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 58200 KB Output is correct
2 Correct 9 ms 62300 KB Output is correct
3 Correct 8 ms 62408 KB Output is correct
4 Correct 8 ms 58200 KB Output is correct
5 Correct 8 ms 60256 KB Output is correct
6 Correct 9 ms 62300 KB Output is correct
7 Correct 8 ms 58204 KB Output is correct
8 Correct 9 ms 60252 KB Output is correct
9 Correct 8 ms 60248 KB Output is correct
10 Correct 8 ms 58204 KB Output is correct
11 Correct 10 ms 58204 KB Output is correct
12 Correct 11 ms 58224 KB Output is correct
13 Correct 8 ms 62300 KB Output is correct
14 Correct 9 ms 58204 KB Output is correct
15 Correct 8 ms 60252 KB Output is correct
16 Correct 7 ms 58204 KB Output is correct
17 Correct 8 ms 60252 KB Output is correct
18 Correct 8 ms 60252 KB Output is correct
19 Correct 9 ms 62300 KB Output is correct
20 Correct 8 ms 62348 KB Output is correct
21 Correct 9 ms 62432 KB Output is correct
22 Correct 8 ms 62420 KB Output is correct
23 Correct 10 ms 58460 KB Output is correct
24 Correct 12 ms 62516 KB Output is correct
25 Correct 12 ms 58460 KB Output is correct
26 Correct 12 ms 62556 KB Output is correct
27 Correct 12 ms 62556 KB Output is correct
28 Correct 14 ms 62360 KB Output is correct
29 Correct 12 ms 60508 KB Output is correct
30 Correct 11 ms 58488 KB Output is correct
31 Correct 11 ms 62600 KB Output is correct
32 Correct 11 ms 62556 KB Output is correct
33 Correct 11 ms 62556 KB Output is correct
34 Correct 11 ms 58476 KB Output is correct
35 Correct 11 ms 58456 KB Output is correct
36 Correct 11 ms 62556 KB Output is correct
37 Correct 11 ms 62556 KB Output is correct
38 Correct 10 ms 58460 KB Output is correct
39 Correct 13 ms 62556 KB Output is correct
40 Correct 10 ms 60516 KB Output is correct
41 Correct 10 ms 58456 KB Output is correct
42 Correct 13 ms 62552 KB Output is correct
43 Correct 11 ms 62556 KB Output is correct
44 Correct 11 ms 62556 KB Output is correct
45 Correct 527 ms 139604 KB Output is correct
46 Correct 520 ms 139344 KB Output is correct
47 Correct 566 ms 139372 KB Output is correct
48 Correct 511 ms 139676 KB Output is correct
49 Correct 497 ms 139092 KB Output is correct
50 Correct 509 ms 139304 KB Output is correct
51 Correct 505 ms 139092 KB Output is correct
52 Correct 538 ms 139600 KB Output is correct
53 Correct 540 ms 139424 KB Output is correct
54 Correct 469 ms 152912 KB Output is correct
55 Correct 428 ms 152064 KB Output is correct
56 Correct 439 ms 150160 KB Output is correct
57 Correct 436 ms 147028 KB Output is correct
58 Correct 378 ms 147008 KB Output is correct
59 Correct 374 ms 146768 KB Output is correct
60 Correct 272 ms 163176 KB Output is correct
61 Correct 398 ms 140796 KB Output is correct
62 Correct 453 ms 155284 KB Output is correct
63 Correct 397 ms 139980 KB Output is correct
64 Correct 355 ms 140240 KB Output is correct
65 Correct 462 ms 155748 KB Output is correct
66 Correct 356 ms 139724 KB Output is correct