Submission #1160637

#	Time	Username	Problem	Language	Result	Execution time	Memory
1160637		fzyzzz_z	Two Dishes (JOI19_dishes)	C++20	Compilation error	0 ms	0 KiB

dishes

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int N = (1LL << 20); 
ll tree[2 * N];
const int ID = 0; 
void init() {
    for (int i = 0; i < 2 * N; ++i) {
        tree[i] = ID; 
    }
}
ll query(int l, int r, int ind = 1, int L = 0, int R = N - 1) {
    if (l <= L && R <= r) {
        return tree[ind]; 
    } if (l > R || L > r) {
        return ID; 
    }

    int M = (L + R) / 2; 
    return max(query(l, r, 2 * ind, L, M), query(l, r, 2 * ind + 1, M + 1, R)); 
}
void update(int x, ll v, int ind = 1, int L = 0, int R = N - 1) {
    if (L > x || x > R) {
        return; 
    }
    if (L == x && x == R) {
        tree[ind] = max(tree[ind], v);  
        return; 
    }

    int M = (L + R) / 2; 
    update(x, v, 2 * ind, L, M); 
    update(x, v, 2 * ind + 1, M + 1, R); 

    tree[ind] = max(tree[2 * ind + 1], tree[2 * ind]); 
}

array<ll, 3> a[N], b[N]; 
ll pa[N], pb[N];  

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    init(); 

    int n, m; 
    cin >> n >> m; 

    // {time, req, score}
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < 3; ++j) {
            cin >> a[i][j]; 
        }
    }
    for (int i = 0; i < m; ++i) {
        for (int j = 0; j < 3; ++j) {
            cin >> b[i][j]; 
        }
    }
    for (int i = 0; i < n; ++i) {
        pa[i + 1] = pa[i] + a[i][0]; 
    }
    for (int i = 0; i < m; ++i) {
        pb[i + 1] = pb[i] + b[i][0]; 
    }

    ll ans = 0; 
    // edges[i] : {time, dir, score} -1 means A[i]->B 
    vector<vector<array<ll, 3>>> edges(n); 


    for (int i = 0; i < n; ++i) {
        auto can_get = [&] (int x) -> bool { // can process x'th from B and still get award for A[i]
            return pb[x + 1] + pa[i + 1] <= a[i][1]; 
        }; 
        if (can_get(m - 1)) {
            ans += a[i][2]; 
            continue; 
        } 
        if (!can_get(0)) {
            continue; 
        }
        int lo = 0, hi = m - 1; 
        while (lo < hi) {
            int md = (lo + hi + 1) / 2; 
            if (can_get(md)) lo = md; 
            else hi = md - 1; 
        }
        if (a[i][2] > 0) { // do A[i] before B[lo + 1]
            edges[i].push_back({lo + 1, -1, a[i][2]}); 
        } else { // do B[lo + 1] before A[i] 
            ans += a[i][2];  
            edges[i].push_back({lo + 1, 1, -a[i][2]}); 
        }
    }
    
    for (int i = 0; i < m; ++i) {
        auto can_get = [&] (int x) -> bool { 
            return pa[x + 1] + pb[i + 1] <= b[i][1]; 
        }; 
        if (can_get(n - 1)) {
            ans += b[i][2]; 
            continue; 
        } 
        if (!can_get(0)) {
            continue; 
        }
        int lo = 0, hi = n - 1; 
        while (lo < hi) {
            int md = (lo + hi + 1) / 2; 
            if (can_get(md)) lo = md; 
            else hi = md - 1; 
        }
        if (b[i][2] > 0) { // do B[i] before A[lo + 1]
            edges[lo + 1].push_back({i, 1, b[i][2]}); 
        } else { // do A[lo + 1] before B[i] 
            ans += b[i][2];  
            edges[lo + 1].push_back({i, -1, -b[i][2]}); 
        }
    }

    // segtree[x] after time t stores dp(first t from A, x from B), 1B

    for (int t = 0; t < n; ++t) {
        sort(edges[t].begin(), edges[t].end());
        vector<pair<ll, ll>> to_upd; 

        // cout << "!! " << t << '\n'; 

        ll dp = 0, dp2 = 0; 
        for (auto [at, dir, w]: edges[t]) {
            if (dir == -1) { // outwards 
                dp2 = max(dp2, dp) + w; 

                to_upd.push_back({at + 1, dp2}); 
            } else { // inwards 
                dp = max(dp, query(0, at + 1)) + w; 

                to_upd.push_back({at + 1, dp}); 
            }

            // cout << "? " << at << ' ' << dir << ' ' << w << '\n'; 
        }

        for (auto [x, v]: to_upd) {
            update(x, v); 

            // cout << "upd " << x << ' ' << v << '\n';
        }
    }

    cout << (ans + query(0, m)) << '\n'; 





    return 0;
}
ce

Compilation message (stderr)

dishes.cpp:163:1: error: 'ce' does not name a type
  163 | ce
      | ^~