oj.uz

Submission #414948

# Submission time Handle Problem Language Result Execution time Memory
414948 2021-05-31T10:58:02 Z Pro_ktmr Constellation 3 (JOI20_constellation3) C++17
100 / 100
 1325 ms 81532 KB 
#pragma GCC target ("avx")
#pragma GCC optimize ("unroll-loops")
#pragma GCC optimize ("O3")

#include"bits/stdc++.h"
#include<unordered_set>
#include<unordered_map>
#include<random>
using namespace std;
typedef long long ll;
const ll MOD = (ll)(1e9+7);
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(), (x).end()
#define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
int dx[4]={ 1,0,-1,0 };
int dy[4]={ 0,1,0,-1 };

struct RMaxQ{
private:
    int N;
    vector<long long> node, lazy;
    long long DEFAULT;
public:
    void init(int n, long long def=-9223372036854775807LL){
        DEFAULT = def;
        N = 1;
        while(N < n) N = (N<<1);
        node.assign(2*N-1, DEFAULT);
        lazy.assign(2*N-1, 0);
    }
    void eval(int k, int l, int r){
        node[k] += lazy[k];
        if(r-l > 1){
            lazy[(k<<1)+1] += lazy[k];
            lazy[(k<<1)+2] += lazy[k];
        }
        lazy[k] = 0LL;
    }
    void add(int a, long long x){
        add(a, a+1, x);
    }
    void add(int a, int b, long long x, int k=0, int l=0, int r=-1){
        if(a >= b) return;
        if(r == -1) r = N;
        eval(k, l, r);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b){
            lazy[k] += x;
            eval(k, l, r);
        }
        else{
            add(a, b, x, (k<<1)+1, l, (l+r)>>1);
            add(a, b, x, (k<<1)+2, (l+r)>>1, r);
            node[k] = std::max(node[(k<<1)+1], node[(k<<1)+2]);
        }
    }
    long long max(int a, int b, int k=0, int l=0, int r=-1){
        if(a >= b) return -9223372036854775807LL;
        if(r == -1) r = N;
        if(b <= l || r <= a) return -9223372036854775807LL;
        eval(k, l, r);
        if(a <= l && r <= b) return node[k];
        return std::max(max(a, b, (k<<1)+1, l, (l+r)>>1), max(a, b, (k<<1)+2, (l+r)>>1, r));
    }
    long long m;
    int find(int a, int b, int k=0, int l=0, int r=-1){
        if(r == -1){
            m = max(a, b);
            r = N;
        }
        if(r <= a || b <= l) return INT_MAX;
        if(r-l == 1){
            if(node[k] == m) return l;
            else return INT_MAX;
        }
        if(a <= l && r <= b){
            int valueL = max(a, b, (k<<1)+1, l, (l+r)/2);
            int valueR = max(a, b, (k<<1)+2, (l+r)/2, r);
            if(valueL == m) return find(a, b, (k<<1)+1, l, (l+r)>>1);
            if(valueR == m) return find(a, b, (k<<1)+2, (l+r)>>1, r);
            return INT_MAX;
        }
        return std::min(find(a, b, (k<<1)+1, l, (l+r)>>1), find(a, b, (k<<1)+2, (l+r)>>1, r));
    }
    long long operator [](int a){
        return max(a, a+1);
    }
};

struct RMinQ{
private:
    int N;
    vector<long long> node, lazy;
    vector<bool> lazyFlg;
    long long DEFAULT;
public:
    void init(int n, long long def=9223372036854775807LL){
        DEFAULT = def;
        N = 1;
        while(N < n) N = (N<<1);
        node.assign(2*N-1, DEFAULT);
        lazy.assign(2*N-1, 0);
        lazyFlg.assign(2*N-1, false);
    }
    void eval(int k, int l, int r){
        if(lazyFlg[k]){
            node[k] = lazy[k];
            if(r-l > 1){
                lazy[(k<<1)+1] = lazy[k];
                lazyFlg[(k<<1)+1] = true;
                lazy[(k<<1)+2] = lazy[k];
                lazyFlg[(k<<1)+2] = true;
            }
            lazy[k] = 0LL;
            lazyFlg[k] = false;
        }
    }
    void update(int a, long long x){
        update(a, a+1, x);
    }
    void update(int a, int b, long long x, int k=0, int l=0, int r=-1){
        if(a >= b) return;
        if(r == -1) r = N;
        eval(k, l, r);
        if(b <= l || r <= a) return;
        if(a <= l && r <= b){
            lazy[k] = x;
            lazyFlg[k] = true;
            eval(k, l, r);
        }
        else{
            update(a, b, x, (k<<1)+1, l, (l+r)>>1);
            update(a, b, x, (k<<1)+2, (l+r)>>1, r);
            node[k] = std::min(node[(k<<1)+1], node[(k<<1)+2]);
        }
    }
    long long min(int a, int b, int k=0, int l=0, int r=-1){
        if(a >= b) return 9223372036854775807LL;
        if(r == -1) r = N;
        if(b <= l || r <= a) return 9223372036854775807LL;
        eval(k, l, r);
        if(a <= l && r <= b) return node[k];
        return std::min(min(a, b, (k<<1)+1, l, (l+r)>>1), min(a, b, (k<<1)+2, (l+r)>>1, r));
    }
    long long m;
    int find(int a, int b, int k=0, int l=0, int r=-1){
        if(r == -1){
            m = min(a, b);
            r = N;
        }
        if(r <= a || b <= l) return INT_MAX;
        if(r-l == 1){
            if(node[k] == m) return l;
            else return INT_MAX;
        }
        if(a <= l && r <= b){
            int valueL = min(a, b, (k<<1)+1, l, (l+r)/2);
            int valueR = min(a, b, (k<<1)+2, (l+r)/2, r);
            if(valueL == m) return find(a, b, (k<<1)+1, l, (l+r)>>1);
            if(valueR == m) return find(a, b, (k<<1)+2, (l+r)>>1, r);
            return INT_MAX;
        }
        return std::min(find(a, b, (k<<1)+1, l, (l+r)>>1), find(a, b, (k<<1)+2, (l+r)>>1, r));
    }
};

int N;
RMaxQ A;
int M;
int X[200000], Y[200000], C[200000];
ll sumC = 0;

vector<pair<int,int>> s[200000]; // stars for each x
RMinQ rmq; int c[200000] ={};
int bottomNode[200000]; // bottom node for each x

int cnt = 0;
ll dp[200000];
RMaxQ depth;
ll dpChi[200000];
int dfs(int l, int r, int u){
    if(l > r) return -1;
    int n = cnt; cnt++;
    int m = A.find(l, r+1);
    int d = A[m]+1;
    bottomNode[m] = n;

    int chi0 = dfs(l, m-1, d-1);
    int chi1 = dfs(m+1, r, d-1);
    if(chi0 != -1 && chi1 != -1){
        depth.add(chi0, chi1, dp[chi1]);
        depth.add(chi1, cnt, dp[chi0]);
    }

    dp[n] = (chi0 != -1 ? dp[chi0] : 0) + (chi1 != -1 ? dp[chi1] : 0);
    dpChi[n] = dp[n];
    while(rmq.min(l, r+1) <= u){
        int i = rmq.find(l, r+1);
        int b = bottomNode[i];
        dp[n] = max(dp[n], s[i][c[i]].second + depth.max(b, b+1) + dpChi[b]);

        c[i]++;
        if(c[i] < s[i].size()) rmq.update(i, s[i][c[i]].first);
        else rmq.update(i, N+1);
    }

    return n;
}

signed main(){
    scanf("%d", &N);
    A.init(N, 0);
    rep(i, N){
        int a;
        scanf("%d", &a);
        A.add(i, a);
    }
    scanf("%d", &M);
    rep(i, M){
        scanf("%d%d%d", X+i, Y+i, C+i);
        X[i]--;
        s[X[i]].pb({ Y[i], C[i] });
        sumC += C[i];
    }
    rmq.init(N, N+1);
    rep(i, N){
        if(s[i].size() == 0) continue;
        sort(all(s[i]));
        rmq.update(i, s[i][0].first);
    }

    depth.init(N, 0);
    dfs(0, N-1, N);
    printf("%lld\n", sumC-dp[0]);
}

Compilation message

constellation3.cpp: In function 'int dfs(int, int, int)':
constellation3.cpp:204:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  204 |         if(c[i] < s[i].size()) rmq.update(i, s[i][c[i]].first);
      |            ~~~~~^~~~~~~~~~~~~
constellation3.cpp: In function 'int main()':
constellation3.cpp:15:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
constellation3.cpp:214:5: note: in expansion of macro 'rep'
  214 |     rep(i, N){
      |     ^~~
constellation3.cpp:15:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
constellation3.cpp:220:5: note: in expansion of macro 'rep'
  220 |     rep(i, M){
      |     ^~~
constellation3.cpp:15:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   15 | #define rep(i, n) for(int (i)=0; (i)<(int)(n); (i)++)
      |                           ^
constellation3.cpp:227:5: note: in expansion of macro 'rep'
  227 |     rep(i, N){
      |     ^~~
constellation3.cpp:212:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  212 |     scanf("%d", &N);
      |     ~~~~~^~~~~~~~~~
constellation3.cpp:216:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  216 |         scanf("%d", &a);
      |         ~~~~~^~~~~~~~~~
constellation3.cpp:219:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  219 |     scanf("%d", &M);
      |     ~~~~~^~~~~~~~~~
constellation3.cpp:221:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  221 |         scanf("%d%d%d", X+i, Y+i, C+i);
      |         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5068 KB Output is correct
2 Correct 5 ms 5068 KB Output is correct
3 Correct 5 ms 5020 KB Output is correct
4 Correct 5 ms 5068 KB Output is correct
5 Correct 5 ms 5068 KB Output is correct
6 Correct 5 ms 5068 KB Output is correct
7 Correct 5 ms 5020 KB Output is correct
8 Correct 5 ms 5068 KB Output is correct
9 Correct 5 ms 5068 KB Output is correct
10 Correct 5 ms 5068 KB Output is correct
11 Correct 5 ms 5068 KB Output is correct
12 Correct 5 ms 5020 KB Output is correct
13 Correct 5 ms 5068 KB Output is correct
14 Correct 6 ms 5068 KB Output is correct
15 Correct 5 ms 5020 KB Output is correct
16 Correct 5 ms 5068 KB Output is correct
17 Correct 5 ms 5068 KB Output is correct
18 Correct 5 ms 5068 KB Output is correct
19 Correct 5 ms 5024 KB Output is correct
20 Correct 5 ms 5068 KB Output is correct
21 Correct 5 ms 5068 KB Output is correct
22 Correct 5 ms 5068 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5068 KB Output is correct
2 Correct 5 ms 5068 KB Output is correct
3 Correct 5 ms 5020 KB Output is correct
4 Correct 5 ms 5068 KB Output is correct
5 Correct 5 ms 5068 KB Output is correct
6 Correct 5 ms 5068 KB Output is correct
7 Correct 5 ms 5020 KB Output is correct
8 Correct 5 ms 5068 KB Output is correct
9 Correct 5 ms 5068 KB Output is correct
10 Correct 5 ms 5068 KB Output is correct
11 Correct 5 ms 5068 KB Output is correct
12 Correct 5 ms 5020 KB Output is correct
13 Correct 5 ms 5068 KB Output is correct
14 Correct 6 ms 5068 KB Output is correct
15 Correct 5 ms 5020 KB Output is correct
16 Correct 5 ms 5068 KB Output is correct
17 Correct 5 ms 5068 KB Output is correct
18 Correct 5 ms 5068 KB Output is correct
19 Correct 5 ms 5024 KB Output is correct
20 Correct 5 ms 5068 KB Output is correct
21 Correct 5 ms 5068 KB Output is correct
22 Correct 5 ms 5068 KB Output is correct
23 Correct 10 ms 5324 KB Output is correct
24 Correct 11 ms 5288 KB Output is correct
25 Correct 10 ms 5284 KB Output is correct
26 Correct 10 ms 5324 KB Output is correct
27 Correct 10 ms 5324 KB Output is correct
28 Correct 10 ms 5324 KB Output is correct
29 Correct 10 ms 5268 KB Output is correct
30 Correct 10 ms 5324 KB Output is correct
31 Correct 10 ms 5276 KB Output is correct
32 Correct 13 ms 5592 KB Output is correct
33 Correct 13 ms 5528 KB Output is correct
34 Correct 11 ms 5452 KB Output is correct
35 Correct 11 ms 5452 KB Output is correct
36 Correct 11 ms 5540 KB Output is correct
37 Correct 11 ms 5536 KB Output is correct
38 Correct 9 ms 5668 KB Output is correct
39 Correct 11 ms 5324 KB Output is correct
40 Correct 11 ms 5580 KB Output is correct
41 Correct 11 ms 5288 KB Output is correct
42 Correct 10 ms 5288 KB Output is correct
43 Correct 11 ms 5708 KB Output is correct
44 Correct 10 ms 5324 KB Output is correct

Subtask #3
65.0 / 65.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 5068 KB Output is correct
2 Correct 5 ms 5068 KB Output is correct
3 Correct 5 ms 5020 KB Output is correct
4 Correct 5 ms 5068 KB Output is correct
5 Correct 5 ms 5068 KB Output is correct
6 Correct 5 ms 5068 KB Output is correct
7 Correct 5 ms 5020 KB Output is correct
8 Correct 5 ms 5068 KB Output is correct
9 Correct 5 ms 5068 KB Output is correct
10 Correct 5 ms 5068 KB Output is correct
11 Correct 5 ms 5068 KB Output is correct
12 Correct 5 ms 5020 KB Output is correct
13 Correct 5 ms 5068 KB Output is correct
14 Correct 6 ms 5068 KB Output is correct
15 Correct 5 ms 5020 KB Output is correct
16 Correct 5 ms 5068 KB Output is correct
17 Correct 5 ms 5068 KB Output is correct
18 Correct 5 ms 5068 KB Output is correct
19 Correct 5 ms 5024 KB Output is correct
20 Correct 5 ms 5068 KB Output is correct
21 Correct 5 ms 5068 KB Output is correct
22 Correct 5 ms 5068 KB Output is correct
23 Correct 10 ms 5324 KB Output is correct
24 Correct 11 ms 5288 KB Output is correct
25 Correct 10 ms 5284 KB Output is correct
26 Correct 10 ms 5324 KB Output is correct
27 Correct 10 ms 5324 KB Output is correct
28 Correct 10 ms 5324 KB Output is correct
29 Correct 10 ms 5268 KB Output is correct
30 Correct 10 ms 5324 KB Output is correct
31 Correct 10 ms 5276 KB Output is correct
32 Correct 13 ms 5592 KB Output is correct
33 Correct 13 ms 5528 KB Output is correct
34 Correct 11 ms 5452 KB Output is correct
35 Correct 11 ms 5452 KB Output is correct
36 Correct 11 ms 5540 KB Output is correct
37 Correct 11 ms 5536 KB Output is correct
38 Correct 9 ms 5668 KB Output is correct
39 Correct 11 ms 5324 KB Output is correct
40 Correct 11 ms 5580 KB Output is correct
41 Correct 11 ms 5288 KB Output is correct
42 Correct 10 ms 5288 KB Output is correct
43 Correct 11 ms 5708 KB Output is correct
44 Correct 10 ms 5324 KB Output is correct
45 Correct 842 ms 46356 KB Output is correct
46 Correct 841 ms 46236 KB Output is correct
47 Correct 839 ms 46636 KB Output is correct
48 Correct 853 ms 46100 KB Output is correct
49 Correct 821 ms 46080 KB Output is correct
50 Correct 833 ms 45992 KB Output is correct
51 Correct 835 ms 46164 KB Output is correct
52 Correct 847 ms 46548 KB Output is correct
53 Correct 835 ms 46276 KB Output is correct
54 Correct 1325 ms 71468 KB Output is correct
55 Correct 1290 ms 64644 KB Output is correct
56 Correct 1275 ms 60748 KB Output is correct
57 Correct 1244 ms 58308 KB Output is correct
58 Correct 1254 ms 64100 KB Output is correct
59 Correct 1238 ms 63808 KB Output is correct
60 Correct 710 ms 81532 KB Output is correct
61 Correct 971 ms 45868 KB Output is correct
62 Correct 1292 ms 75536 KB Output is correct
63 Correct 985 ms 46080 KB Output is correct
64 Correct 969 ms 45576 KB Output is correct
65 Correct 1307 ms 75780 KB Output is correct
66 Correct 996 ms 46072 KB Output is correct