Submission #679537

#	Time	Username	Problem	Language	Result	Execution time	Memory
679537		keta_tsimakuridze	Two Dishes (JOI19_dishes)	C++14	100 / 100	8328 ms	282712 KiB

dishes

#include<bits/stdc++.h>
#define f first
#define s second
#define int long long
#define pii pair<int,int>
using namespace std;
const int N = 1e6 + 5, mod = 1e9 + 7, inf = 1e18; // !
int lazy[4 * N][2], a[N][2], c[N][2], s[N][2], n[2];
vector<pii> x[N];
int t[4 * N];
int merge(int x, int y) {
    return max(x, y);
}
void push(int u, int l, int r) {
    if(lazy[u][0] != -inf) {
        t[u] = lazy[u][0];
        if(l < r) {
            lazy[2 * u][1] = lazy[2 * u + 1][1] = 0;
            lazy[2 * u][0] = lazy[2 * u + 1][0] = lazy[u][0];
        }
        lazy[u][0] = -inf;
    }
    if(lazy[u][1] != 0) {
        t[u] += lazy[u][1];
        if(l < r) {
            lazy[2 * u][1] += lazy[u][1];
            lazy[2 * u + 1][1] += lazy[u][1];
        }
        lazy[u][1] = 0;
    }
}
void upd(int u, int st, int en, int l, int r, int x, int T) {
    push(u, l, r);
    if(l > en || r < st) return;
    if(st <= l && r <= en) {
        lazy[u][T] = x;
        push(u, l, r);
        return;
    }
    int mid = (l + r) / 2;
    upd(2 * u, st, en, l, mid, x, T); upd(2 * u + 1, st, en, mid + 1, r, x, T);
    t[u] = merge(t[2 * u], t[2 * u + 1]);
}
int get(int u, int st, int en, int l, int r) {
    push(u, l, r);
    if(l > en || r < st) return -inf;
    if(st <= l && r <= en) return t[u];
    int mid = (l + r) / 2;

    int x = merge(get(2 * u, st, en, l, mid), get(2 * u + 1, st, en, mid + 1, r));
    t[u] = merge(t[2 * u], t[2 * u + 1]);
    return x;
}
int GET(int u, int L, int l, int r, int x) {
    if(l == r) {
        if(t[u] < x) return l + 1;
        return l;
    }
    int mid = (l + r) /2;
    push(2 * u, l, mid);
    push(2 * u + 1, mid + 1, r);
    if(l >= L) {

        if(t[2 * u] < x) return GET(2 * u + 1, L, mid + 1, r, x);
        return GET(2 * u,  L, l, mid, x);
    }
    if(mid < L) return GET(2 * u + 1, L, mid + 1, r, x);
    int id = GET(2 * u, L, l, mid, x);
    if(id == mid + 1) return GET(2 * u + 1, L, mid + 1, r, x);
    else return id;
}
main(){
    ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0);
    int  m;
    cin >> n[0] >> n[1];
    for(int t = 0; t < 2; t++) {
        for(int i = 1; i <= n[t]; i++) {
            cin >> a[i][t] >> s[i][t] >> c[i][t];
            a[i][t] += a[i - 1][t];
        }
    }
    int ans = 0;
    for(int t = 0; t < 2; t++) {
        int R = n[t^1];
        for(int i = 1; i <= n[t]; i++) {

            int l = 0, r = n[t^1], R = -1;

            while(l <= r) {
                int mid = (l + r) / 2;
                if(a[i][t] + a[mid][t^1] <= s[i][t]) R = mid, l = mid + 1;
                else r = mid - 1;
            }
            if(!t) {
                // R tu aris i - s win mashin ver vigebt
                ++R;
                ans += c[i][t];
                if(R == n[1] + 1) continue;
                x[i].push_back({R, -c[i][t]});
                continue;
            }
            ++R;
            if(R == n[0] + 1) {
                ans += c[i][t];
                continue;
            }
            // R tu aris i - s shemdeg mashin vigebt
            // i tu aris R - is win mashin vigebt

            x[R].push_back({i, c[i][t]});
        }
    }
/*
    vector<int> dp(n[1] + 1);
    for(int i = 1; i <= n[0]; i++) {
        for(int j = 1; j <= n[1]; j++) dp[j] = max(dp[j], dp[j - 1]);
        sort(x[i].begin(), x[i].end());

        for(int k = 0; k < x[i].size(); k++) {
            for(int j = x[i][k].f; j <= n[1]; j++) dp[j] += x[i][k].s;
        }
    }
    int mn = -inf;
    for(int i = 0; i <= n[1]; i++) mn = max(mn, dp[i]);
    cout << ans + mn << "\n";
    return 0; */
//    build(1, 0, n[1]);
    for(int i = 1; i <= n[0]; i++) {
        x[i].push_back({0, 0});
        x[i].push_back({n[1] + 1, 0});
        sort(x[i].begin(), x[i].end());
        int c = 0, mx = -inf;
        vector<int> v;
        for(int j = 0; j + 1 < x[i].size(); j++) {
            c += x[i][j].s;
            if(x[i][j + 1].f != x[i][j].f) {
                upd(1, x[i][j].f, -1 + x[i][j + 1].f, 0, n[1], c, 1);
                int mx = get(1, 0, x[i][j].f - 1, 0, n[1]);
                int id = min(-1 + x[i][j + 1].f, GET(1, x[i][j].f, 0, n[1], mx) - 1);
//                cout << mx << " __ " << id << endl;
                upd(1, x[i][j].f, id, 0, n[1], mx, 0);
            }
        }
    }
    cout << t[1] + ans;

 }
 /*
 4 3
2 1 1
3 8 1
2 13 1
1 13 1
3 6 1
2 11 1
2 15 1
-1000000000000000000__-1
-1000000000000000000__-1
-1__0
0__3
-1000000000000000000__-1
0__1
1__3
-1000000000000000000__-1
1__3
6

 */

Compilation message (stderr)

dishes.cpp:72:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   72 | main(){
      | ^~~~
dishes.cpp: In function 'int main()':
dishes.cpp:84:13: warning: unused variable 'R' [-Wunused-variable]
   84 |         int R = n[t^1];
      |             ^
dishes.cpp:134:30: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |         for(int j = 0; j + 1 < x[i].size(); j++) {
      |                        ~~~~~~^~~~~~~~~~~~~
dishes.cpp:132:20: warning: unused variable 'mx' [-Wunused-variable]
  132 |         int c = 0, mx = -inf;
      |                    ^~
dishes.cpp:74:10: warning: unused variable 'm' [-Wunused-variable]
   74 |     int  m;
      |          ^

• Subtask 1: 5 / 5
• Subtask 2: 3 / 3
• Subtask 3: 7 / 7
• Subtask 4: 39 / 39
• Subtask 5: 11 / 11
• Subtask 6: 9 / 9
• Subtask 7: 17 / 17
• Subtask 8: 9 / 9