Submission #414948

#	Time	Username	Problem	Language	Result	Execution time	Memory
414948		Pro_ktmr	Constellation 3 (JOI20_constellation3)	C++17	100 / 100	1325 ms	81532 KiB

constellation3

#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 (stderr)

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 / 14
• Subtask 2: 21 / 21
• Subtask 3: 65 / 65