Submission #1079531

#	Time	Username	Problem	Language	Result	Execution time	Memory
1079531		phong	Two Dishes (JOI19_dishes)	C++17	100 / 100	4964 ms	353108 KiB

dishes

#include<bits/stdc++.h>

#define ll long long
#define int long long
const int nmax = 1e6 + 5, N = 1e5;
const ll oo = 1e18 + 1, base = 311;
const int lg = 19, M = 10;
const ll mod = 998244353, mod2 = 1e9 + 5277;
#define pii pair<int, int>
#define fi first
#define se second
#define endl "\n"
#define debug(a, n) for(int i = 1; i <= n; ++i) cout << a[i] << ' '; cout << "\n";
using namespace std;

int n, m;
struct node{
    ll x, y, z;
}a[nmax], b[nmax];
map<int, ll> adj[nmax];
ll tree[nmax << 2], tr[nmax << 2];
pii lz[nmax << 2];
void build(int id, int l, int r){
    lz[id] = {1, 0};
    if(l != r){
        int mid = r + l >> 1;
        build(id << 1, l, mid);
        build(id << 1 | 1, mid + 1, r);
    }
}
void fix(int id, pii tx){
//    if(val == -oo) return;
    tree[id] = tree[id] * tx.fi + tx.se;
    tr[id] = tr[id] * tx.fi + tx.se;
    lz[id].fi = lz[id].fi * tx.fi;
    lz[id].se = lz[id].se * tx.fi + tx.se;
}
void down(int id){
    fix(id << 1, lz[id]);
    fix(id << 1 | 1, lz[id]);
    lz[id] = {1, 0};
}
void update(int id, int l, int r, int u, int v, pii val, int k){
    if(l > v || r < u || tr[id] >= k) return;
    if(l >= u && r<= v && tree[id] < k){
        return fix(id, val);
    }
    down(id);
    int mid = r + l >> 1;
    update(id << 1, l, mid, u, v,val, k);
    update(id << 1 |1, mid + 1, r, u,v, val, k);
    tree[id] = max(tree[id << 1], tree[id << 1 | 1]);
    tr[id] = min(tr[id << 1], tr[id << 1 | 1]);

//    for(int i = u; i <= v; ++i){
//        if(tree[i] > k) continue;
//        tree[i] = tree[i] * val.fi + val.se;
//    }
}
int get(int id, int l, int r, int u, int v){
    if(l >= u && r <=v ) return tree[id];
    int mid = r + l >> 1;
    down(id);
    if(mid < u) return get(id << 1 | 1, mid + 1, r,u, v);
    if(mid + 1 > v) return get(id << 1, l, mid, u, v);
    return max(get(id << 1, l, mid, u, v), get(id << 1 | 1, mid + 1, r, u, v));
//    int ma = -oo;
//    for(int i = u; i <= v; ++i) ma = max(ma, tree[i]);
//    return ma;
}
main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
//    freopen("code.inp", "r", stdin);
//    freopen("code.out", "w", stdout);
    cin >> n >> m;
    for(int i = 1; i <= n; ++i) cin >> a[i].x >> a[i].y >> a[i].z, a[i].x += a[i - 1].x;
    for(int i = 1; i <= m; ++i) cin >> b[i].x >> b[i].y >> b[i].z, b[i].x += b[i - 1].x;
    ll ans  = 0;
    for(int i = 1; i <= n; ++i){
        if(a[i].x <= a[i].y){
            int l = 1, r = m, it = m + 1;
            while(l <= r){
                int mid = r + l >> 1;
                if(b[mid].x > a[i].y - a[i].x){
                    r = mid - 1;
                    it = mid;
                }
                else l = mid + 1;
            }
            ans += a[i].z;
            if(it <= m) adj[i][it] -= a[i].z;
        }
    }
    for(int i = 1; i <= m; ++i){

        if(b[i].x <= b[i].y){
            int l = 1, r = n, it = n + 1;
            while(l <= r){
                int mid = r + l >> 1;
                if(a[mid].x > b[i].y - b[i].x){
                    r = mid - 1;
                    it = mid;
                }
                else l = mid + 1;
            }
//             cout << i << ' ' << it << endl;
            if(it > n) ans += b[i].z;
            else adj[it][i] += b[i].z;
        }
    }
//    memset(dp, -63, sizeof dp);
//    dp[0][0] = 0;
    build(1, 0, m);
    vector<pii> tmp;
    for(int i = 1; i <= n; ++i){

        ll sum = 0;
        for(auto [j, val] : adj[i]){
//            sum += val;
             update(1, 0, m, j, m, {1, val}, oo);
//            if(i == 3) cout <<get(1, 0, m, 0, j) << ' ';
            tmp.push_back({get(1, 0, m, 0, j), j});
        }
        sort(tmp.begin(), tmp.end());
        for(auto [val, j] : tmp){
             update(1, 0, m, j, m, {0, val}, val);
        }
//        for(int j = 0; j <= m; ++j) cout << get(1, 0, m, j, j) << ' ';
//        cout << endl;
        tmp.clear();
    }
    cout << tree[1] + ans;

}
/*
5
10 2 4
1 1 1
2 1 3
1 1 1
100 1 1
1
1 3
*/

Compilation message (stderr)

dishes.cpp: In function 'void build(long long int, long long int, long long int)':
dishes.cpp:26:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   26 |         int mid = r + l >> 1;
      |                   ~~^~~
dishes.cpp: In function 'void update(long long int, long long int, long long int, long long int, long long int, std::pair<long long int, long long int>, long long int)':
dishes.cpp:49:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   49 |     int mid = r + l >> 1;
      |               ~~^~~
dishes.cpp: In function 'long long int get(long long int, long long int, long long int, long long int, long long int)':
dishes.cpp:62:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   62 |     int mid = r + l >> 1;
      |               ~~^~~
dishes.cpp: At global scope:
dishes.cpp:71:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   71 | main(){
      | ^~~~
dishes.cpp: In function 'int main()':
dishes.cpp:84:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   84 |                 int mid = r + l >> 1;
      |                           ~~^~~
dishes.cpp:100:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  100 |                 int mid = r + l >> 1;
      |                           ~~^~~
dishes.cpp:118:12: warning: unused variable 'sum' [-Wunused-variable]
  118 |         ll sum = 0;
      |            ^~~

• 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