Submission #212479

#	Time	Username	Problem	Language	Result	Execution time	Memory
212479		BThero	Constellation 3 (JOI20_constellation3)	C++17	35 / 100	1381 ms	524292 KiB

constellation3

#define DBG 1
// chrono::system_clock::now().time_since_epoch().count()
#include<bits/stdc++.h>
//#include<ext/pb_ds/tree_policy.hpp>
//#include<ext/pb_ds/assoc_container.hpp>

#define pb push_back
#define eb emplace_back
#define mp make_pair
#define fi first
#define se second
#define all(x) (x).begin(), (x).end()
#define debug(x) if (DBG) cerr << #x << " = " << x << endl;

using namespace std;
//using namespace __gnu_pbds;

typedef long long ll;
typedef pair<int, int> pii;

//template<typename T> using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int MAXN = (int)2e5 + 5;

struct Node {
    Node *c1, *c2;
    ll x;
    int sz;
    
    Node() {
        c1 = c2 = 0;
        x = sz = 0;
    }
} *root[MAXN];

pii t[MAXN << 2];
vector<pii> S[MAXN];
ll dp[MAXN];
vector<int> adj[MAXN];
pii seg[MAXN];
int n, m, sz;
int arr[MAXN];

void ptUpd(Node *&v, int tl, int tr, int p, ll x) {
    if (p < tl || p > tr) {
        return;
    } 
    
    if (!v) {
        v = new Node();
        v -> x = 0;
        v -> sz = 1;
    }
    
    v -> x += x;
    
    if (tl == tr) {
        return;
    }
    
    int mid = (tl + tr) >> 1;
    
    if (p <= mid) {
        ptUpd(v -> c1, tl, mid, p, x);
    }
    else {
        ptUpd(v -> c2, mid + 1, tr, p, x);
    }
    
    v -> sz = 0;
    
    if (v -> c1) {
        v -> sz += v -> c1 -> sz;
    }
    
    if (v -> c2) {
        v -> sz += v -> c2 -> sz;
    }
}

ll segSum(Node *&v, int tl, int tr, int l, int r) {
    if (l > r || tl > r || tr < l || !v) {
        return 0;
    }
    
    if (l <= tl && tr <= r) {
        return v -> x;
    }
    
    int mid = (tl + tr) >> 1;
    return segSum(v -> c1, tl, mid, l, r)
    + segSum(v -> c2, mid + 1, tr, l, r);
}

void mergeT(Node *&v, Node *&v2) {
    if (!v2) {
        return;
    }
    
    if (!v) {
        v = v2;
        return;
    }
    
    v -> x += v2 -> x;
    mergeT(v -> c1, v2 -> c1);
    mergeT(v -> c2, v2 -> c2);
    
    v -> sz = 0;
    
    if (v -> c1) {
        v -> sz += v -> c1 -> sz;
    }
    
    if (v -> c2) {
        v -> sz += v -> c2 -> sz;
    }
}

void build(int v, int tl, int tr) {
    if (tl == tr) {
        t[v] = mp(arr[tl], tl);
        return;
    }
    
    int mid = (tl + tr) >> 1;
    int c1 = (v << 1), c2 = (c1 | 1);
    
    build(c1, tl, mid);
    build(c2, mid + 1, tr);
    
    t[v] = max(t[c1], t[c2]);
}

pii segMax(int v, int tl, int tr, int l, int r) {
    if (l > r || tl > r || tr < l) {
        return mp(-1, 0);
    }
    
    if (l <= tl && tr <= r) {
        return t[v];
    }
    
    int mid = (tl + tr) >> 1;
    int c1 = (v << 1), c2 = (c1 | 1);
    
    return max(segMax(c1, tl, mid, l, r), segMax(c2, mid + 1, tr, l, r));
}

void del(int v, int tl, int tr, int p) {
    if (tl == tr) {
        t[v] = mp(-1, tl);
        return;
    }
    
    int mid = (tl + tr) >> 1;
    int c1 = (v << 1), c2 = (c1 | 1);
    
    if (p <= mid) {
        del(c1, tl, mid, p);
    }
    else {
        del(c2, mid + 1, tr, p);
    }
    
    t[v] = max(t[c1], t[c2]);
}

ll go(int v, int x) {
    if (seg[v].fi > x || seg[v].se < x) {
        return dp[v];
    }
    
    ll ret = 0;
    
    for (int to : adj[v]) {
        ret += go(to, x);
    }
    
    return ret;
}

int calc(int l, int r, int h = n) {
    int v = ++sz;
    seg[v] = mp(l, r);
    pii tmp = segMax(1, 1, n, l, r);
    int mx = tmp.fi;
    vector<int> hi;
    hi.pb(tmp.se);
    hi.pb(l - 1);
    hi.pb(r + 1);
    del(1, 1, n, tmp.se);
    
    while (1) {
        tmp = segMax(1, 1, n, l, r);
        
        if (tmp.fi < mx) {
            break;
        }
        
        hi.pb(tmp.se);
        del(1, 1, n, tmp.se);
    }
    
    sort(all(hi));
    ll best = 0;
    vector<int> opt(r - l + 1, -1);
    
    for (int i = 0; i + 1 < hi.size(); ++i) {
        if (i > 0) {
            int x = hi[i];
            
            while (!S[x].empty()) {
                best = max(best, (ll)S[x].back().se);
                S[x].pop_back();
            }
        }
        
        int cl = hi[i] + 1;
        int cr = hi[i + 1] - 1;
        
        if (cl <= cr) {        
            for (int x = cl; x <= cr; ++x) {
                while (!S[x].empty() && S[x].back().fi > mx) {
                    opt[x - l] = max(opt[x - l], S[x].back().se);
                    S[x].pop_back();
                } 
            }
        
            int to = calc(cl, cr, mx);
            adj[v].pb(to);
            dp[v] += dp[to];
        
            for (int x = cl; x <= cr; ++x) {
                if (opt[x - l] != -1) {
                    best = max(best, -dp[to] + opt[x - l] + segSum(root[to], 1, n, 1, x));
                }
            }
            
            if (!root[v] || root[v] -> sz < root[to] -> sz) {
                swap(root[v], root[to]);
            }
            
            mergeT(root[v], root[to]);
        }
    }
    
    dp[v] += best;
    ptUpd(root[v], 1, n, 1, best);
    ptUpd(root[v], 1, n, l, -best);
    ptUpd(root[v], 1, n, r + 1, best);
    return v;
}

void solve() {
	scanf("%d", &n);
    
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &arr[i]);
    }
    
    ll sum = 0;
    scanf("%d", &m);
    
    for (int i = 1; i <= m; ++i) {
        int x, y, c;
        scanf("%d %d %d", &x, &y, &c);
        S[x].pb(mp(y, c));
        sum += c;
    }
    
    for (int i = 1; i <= n; ++i) {
        sort(all(S[i]));
    }
    
    build(1, 1, n);
    printf("%lld\n", sum - dp[calc(1, n)]);
}

int main() {
	int tt = 1;
	
	while (tt--) {
		solve();
	}

	return 0;
}

Compilation message (stderr)

constellation3.cpp: In function 'int calc(int, int, int)':
constellation3.cpp:209:27: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i + 1 < hi.size(); ++i) {
                     ~~~~~~^~~~~~~~~~~
constellation3.cpp: In function 'void solve()':
constellation3.cpp:256:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
  ~~~~~^~~~~~~~~~
constellation3.cpp:259:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d", &arr[i]);
         ~~~~~^~~~~~~~~~~~~~~
constellation3.cpp:263:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &m);
     ~~~~~^~~~~~~~~~
constellation3.cpp:267:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %d %d", &x, &y, &c);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~

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