oj.uz

Submission #999517

# Submission time Handle Problem Language Result Execution time Memory
999517 2024-06-15T16:38:45 Z snpmrnhlol Constellation 3 (JOI20_constellation3) C++17
100 / 100
 372 ms 113180 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 2e5;
const int G = 2*N;
const int logN = 20;
int n,m;
vector <int> e[G];
int v[N];
vector <int> lefte[N + 1];
vector <int> righte[N + 1];
int prleft[N + 1][logN],prright[N + 1][logN];
int subleft[N + 1],subright[N + 1];
int leftside[N + 1],rightside[N + 1];
///bear your fangs its time to fight
///pa pa pa parade in shame tonight
int ordleft[N + 1],ordright[N + 1];
int ord2left[N + 1],ord2right[N + 1];
int cntleft = 0,cntright = 0;
int leftid[N],rightid[N];
ll fenleft[N + 1],fenright[N + 1];
///
int stk[N];
vector <int> p;
struct star{
    int x,y,c;
}v2[N];
vector <int> cand[G];
map<int,pair<int,int>> f;
vector <int> points;
ll dp[G];
int cnt = 0;
void addedge(int u,int w){
    e[u].push_back(w);
}
void addleft(int pos,ll nr){
    for(int i = pos;i <= n;i|=(i + 1)){
        fenleft[i]+=nr;
    }
}
void addright(int pos,ll nr){
    for(int i = pos;i <= n;i|=(i + 1)){
        fenright[i]+=nr;
    }
}
ll getleft(int pos){
    ll r = 0;
    for(int i = pos;i >= 0;i&=(i + 1),i--){
        r+=fenleft[i];
    }
    return r;
}
ll getright(int pos){
    ll r = 0;
    for(int i = pos;i >= 0;i&=(i + 1),i--){
        r+=fenright[i];
    }
    return r;
}
void dfs(int 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;
        int 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){
        addleft(ordleft[ord2left[node]],dp[node]);
        addleft(ordleft[ord2left[node]] + subleft[ord2left[node]],-dp[node]);
    }
    if(ord2right[node] != -1){
        addright(ordright[ord2right[node]],dp[node]);
        addright(ordright[ord2right[node]] + subright[ord2right[node]],-dp[node]);
    }
}
void dfsleft(int node, int 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(int node, int 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(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>n;
    p.resize(n);
    for(int i = 0;i < n;i++){
        cin>>v[i];
        p[i] = i;
        leftid[i] = rightid[i] = -1;
    }
    sort(p.begin(),p.end(),[&](int a,int b){
        if(v[a] == v[b])return a < b;
        return v[a] > v[b];
    });
    cin>>m;
    ll sum = 0;
    for(int 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++};
    int pt = 0;
    int pt2 = 0;
    for(int i = n;i >= 1;i--){
        points.clear();
        while(pt2 < n && v[p[pt2]] >= i){
            points.push_back(p[pt2]);
            pt2++;
        }
        int j = 0;
        while(j < points.size()){
            auto it = prev(f.upper_bound(points[j]));
            int k = j;
            while(k < points.size() && points[k] <= it->second.first){
                k++;
            }
            int l = it->first;
            int r = it->second.first;
            int id = it->second.second;
            f.erase(it);
            for(int p = j;p <= k;p++){
                int lside = (p == j?l:points[p - 1] + 1);
                int 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){
            int id = prev(f.upper_bound(v2[pt].x))->second.second;
            cand[id].push_back(pt);
            pt++;
        }
    }
    int cnt2 = 0;
    for(int 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(int 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(int j = 1;j < logN;j++){
        for(int 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:152:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  152 |         while(j < points.size()){
      |               ~~^~~~~~~~~~~~~~~
constellation3.cpp:155:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  155 |             while(k < points.size() && points[k] <= it->second.first){
      |                   ~~^~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 44892 KB Output is correct
2 Correct 7 ms 46912 KB Output is correct
3 Correct 8 ms 46908 KB Output is correct
4 Correct 9 ms 44888 KB Output is correct
5 Correct 8 ms 44892 KB Output is correct
6 Correct 8 ms 46940 KB Output is correct
7 Correct 7 ms 44876 KB Output is correct
8 Correct 7 ms 44892 KB Output is correct
9 Correct 7 ms 44892 KB Output is correct
10 Correct 7 ms 44888 KB Output is correct
11 Correct 7 ms 44892 KB Output is correct
12 Correct 7 ms 44880 KB Output is correct
13 Correct 7 ms 46940 KB Output is correct
14 Correct 8 ms 44892 KB Output is correct
15 Correct 9 ms 46936 KB Output is correct
16 Correct 7 ms 44888 KB Output is correct
17 Correct 7 ms 44888 KB Output is correct
18 Correct 6 ms 46940 KB Output is correct
19 Correct 7 ms 46936 KB Output is correct
20 Correct 7 ms 46940 KB Output is correct
21 Correct 7 ms 46920 KB Output is correct
22 Correct 7 ms 46940 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 44892 KB Output is correct
2 Correct 7 ms 46912 KB Output is correct
3 Correct 8 ms 46908 KB Output is correct
4 Correct 9 ms 44888 KB Output is correct
5 Correct 8 ms 44892 KB Output is correct
6 Correct 8 ms 46940 KB Output is correct
7 Correct 7 ms 44876 KB Output is correct
8 Correct 7 ms 44892 KB Output is correct
9 Correct 7 ms 44892 KB Output is correct
10 Correct 7 ms 44888 KB Output is correct
11 Correct 7 ms 44892 KB Output is correct
12 Correct 7 ms 44880 KB Output is correct
13 Correct 7 ms 46940 KB Output is correct
14 Correct 8 ms 44892 KB Output is correct
15 Correct 9 ms 46936 KB Output is correct
16 Correct 7 ms 44888 KB Output is correct
17 Correct 7 ms 44888 KB Output is correct
18 Correct 6 ms 46940 KB Output is correct
19 Correct 7 ms 46936 KB Output is correct
20 Correct 7 ms 46940 KB Output is correct
21 Correct 7 ms 46920 KB Output is correct
22 Correct 7 ms 46940 KB Output is correct
23 Correct 8 ms 44892 KB Output is correct
24 Correct 9 ms 46940 KB Output is correct
25 Correct 9 ms 44892 KB Output is correct
26 Correct 10 ms 46988 KB Output is correct
27 Correct 10 ms 46940 KB Output is correct
28 Correct 10 ms 47108 KB Output is correct
29 Correct 9 ms 46940 KB Output is correct
30 Correct 10 ms 45048 KB Output is correct
31 Correct 9 ms 46936 KB Output is correct
32 Correct 9 ms 47196 KB Output is correct
33 Correct 9 ms 47196 KB Output is correct
34 Correct 9 ms 45144 KB Output is correct
35 Correct 8 ms 45140 KB Output is correct
36 Correct 8 ms 47196 KB Output is correct
37 Correct 8 ms 47196 KB Output is correct
38 Correct 7 ms 45148 KB Output is correct
39 Correct 10 ms 46936 KB Output is correct
40 Correct 9 ms 47196 KB Output is correct
41 Correct 10 ms 44892 KB Output is correct
42 Correct 9 ms 46940 KB Output is correct
43 Correct 9 ms 47248 KB Output is correct
44 Correct 9 ms 46940 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 44892 KB Output is correct
2 Correct 7 ms 46912 KB Output is correct
3 Correct 8 ms 46908 KB Output is correct
4 Correct 9 ms 44888 KB Output is correct
5 Correct 8 ms 44892 KB Output is correct
6 Correct 8 ms 46940 KB Output is correct
7 Correct 7 ms 44876 KB Output is correct
8 Correct 7 ms 44892 KB Output is correct
9 Correct 7 ms 44892 KB Output is correct
10 Correct 7 ms 44888 KB Output is correct
11 Correct 7 ms 44892 KB Output is correct
12 Correct 7 ms 44880 KB Output is correct
13 Correct 7 ms 46940 KB Output is correct
14 Correct 8 ms 44892 KB Output is correct
15 Correct 9 ms 46936 KB Output is correct
16 Correct 7 ms 44888 KB Output is correct
17 Correct 7 ms 44888 KB Output is correct
18 Correct 6 ms 46940 KB Output is correct
19 Correct 7 ms 46936 KB Output is correct
20 Correct 7 ms 46940 KB Output is correct
21 Correct 7 ms 46920 KB Output is correct
22 Correct 7 ms 46940 KB Output is correct
23 Correct 8 ms 44892 KB Output is correct
24 Correct 9 ms 46940 KB Output is correct
25 Correct 9 ms 44892 KB Output is correct
26 Correct 10 ms 46988 KB Output is correct
27 Correct 10 ms 46940 KB Output is correct
28 Correct 10 ms 47108 KB Output is correct
29 Correct 9 ms 46940 KB Output is correct
30 Correct 10 ms 45048 KB Output is correct
31 Correct 9 ms 46936 KB Output is correct
32 Correct 9 ms 47196 KB Output is correct
33 Correct 9 ms 47196 KB Output is correct
34 Correct 9 ms 45144 KB Output is correct
35 Correct 8 ms 45140 KB Output is correct
36 Correct 8 ms 47196 KB Output is correct
37 Correct 8 ms 47196 KB Output is correct
38 Correct 7 ms 45148 KB Output is correct
39 Correct 10 ms 46936 KB Output is correct
40 Correct 9 ms 47196 KB Output is correct
41 Correct 10 ms 44892 KB Output is correct
42 Correct 9 ms 46940 KB Output is correct
43 Correct 9 ms 47248 KB Output is correct
44 Correct 9 ms 46940 KB Output is correct
45 Correct 368 ms 92240 KB Output is correct
46 Correct 361 ms 92044 KB Output is correct
47 Correct 364 ms 91984 KB Output is correct
48 Correct 370 ms 92304 KB Output is correct
49 Correct 366 ms 91732 KB Output is correct
50 Correct 352 ms 91776 KB Output is correct
51 Correct 366 ms 91732 KB Output is correct
52 Correct 371 ms 92240 KB Output is correct
53 Correct 372 ms 92052 KB Output is correct
54 Correct 294 ms 104276 KB Output is correct
55 Correct 265 ms 100180 KB Output is correct
56 Correct 262 ms 98132 KB Output is correct
57 Correct 261 ms 96592 KB Output is correct
58 Correct 245 ms 95188 KB Output is correct
59 Correct 220 ms 95056 KB Output is correct
60 Correct 138 ms 113180 KB Output is correct
61 Correct 247 ms 90452 KB Output is correct
62 Correct 276 ms 104020 KB Output is correct
63 Correct 232 ms 89684 KB Output is correct
64 Correct 227 ms 89940 KB Output is correct
65 Correct 258 ms 104276 KB Output is correct
66 Correct 224 ms 89428 KB Output is correct