oj.uz

Submission #1079521

# Submission time Handle Problem Language Result Execution time Memory
1079521 2024-08-28T16:20:06 Z phong Two Dishes (JOI19_dishes) C++17
10 / 100
 10000 ms 57780 KB 
#include<bits/stdc++.h>

#define ll long long
#define int long long
const int nmax = 2e5 + 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];
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;
    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) return;
    if(l == r && tree[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]);
//    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

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:60:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   60 |     int mid = r + l >> 1;
      |               ~~^~~
dishes.cpp: At global scope:
dishes.cpp:69:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   69 | main(){
      | ^~~~
dishes.cpp: In function 'int main()':
dishes.cpp:82:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   82 |                 int mid = r + l >> 1;
      |                           ~~^~~
dishes.cpp:98:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   98 |                 int mid = r + l >> 1;
      |                           ~~^~~
dishes.cpp:116:12: warning: unused variable 'sum' [-Wunused-variable]
  116 |         ll sum = 0;
      |            ^~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10015 ms 56796 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 4 ms 9820 KB Output is correct
5 Correct 4 ms 9820 KB Output is correct
6 Correct 4 ms 9820 KB Output is correct
7 Correct 4 ms 9652 KB Output is correct
8 Correct 5 ms 9816 KB Output is correct
9 Correct 5 ms 9820 KB Output is correct
10 Correct 5 ms 9816 KB Output is correct
11 Correct 5 ms 10072 KB Output is correct
12 Correct 4 ms 9820 KB Output is correct
13 Correct 4 ms 9820 KB Output is correct
14 Correct 4 ms 9820 KB Output is correct
15 Correct 5 ms 9820 KB Output is correct
16 Correct 4 ms 9820 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 4 ms 9820 KB Output is correct
5 Correct 4 ms 9820 KB Output is correct
6 Correct 4 ms 9820 KB Output is correct
7 Correct 4 ms 9652 KB Output is correct
8 Correct 5 ms 9816 KB Output is correct
9 Correct 5 ms 9820 KB Output is correct
10 Correct 5 ms 9816 KB Output is correct
11 Correct 5 ms 10072 KB Output is correct
12 Correct 4 ms 9820 KB Output is correct
13 Correct 4 ms 9820 KB Output is correct
14 Correct 4 ms 9820 KB Output is correct
15 Correct 5 ms 9820 KB Output is correct
16 Correct 4 ms 9820 KB Output is correct
17 Correct 6 ms 10076 KB Output is correct
18 Correct 28 ms 10332 KB Output is correct
19 Correct 47 ms 10328 KB Output is correct
20 Correct 23 ms 10328 KB Output is correct
21 Correct 26 ms 10220 KB Output is correct
22 Correct 47 ms 10328 KB Output is correct
23 Correct 47 ms 10332 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 4 ms 9820 KB Output is correct
5 Correct 4 ms 9820 KB Output is correct
6 Correct 4 ms 9820 KB Output is correct
7 Correct 4 ms 9652 KB Output is correct
8 Correct 5 ms 9816 KB Output is correct
9 Correct 5 ms 9820 KB Output is correct
10 Correct 5 ms 9816 KB Output is correct
11 Correct 5 ms 10072 KB Output is correct
12 Correct 4 ms 9820 KB Output is correct
13 Correct 4 ms 9820 KB Output is correct
14 Correct 4 ms 9820 KB Output is correct
15 Correct 5 ms 9820 KB Output is correct
16 Correct 4 ms 9820 KB Output is correct
17 Correct 6 ms 10076 KB Output is correct
18 Correct 28 ms 10332 KB Output is correct
19 Correct 47 ms 10328 KB Output is correct
20 Correct 23 ms 10328 KB Output is correct
21 Correct 26 ms 10220 KB Output is correct
22 Correct 47 ms 10328 KB Output is correct
23 Correct 47 ms 10332 KB Output is correct
24 Correct 226 ms 50708 KB Output is correct
25 Execution timed out 10028 ms 57780 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 4 ms 9820 KB Output is correct
5 Correct 4 ms 9820 KB Output is correct
6 Correct 4 ms 9820 KB Output is correct
7 Correct 4 ms 9652 KB Output is correct
8 Correct 5 ms 9816 KB Output is correct
9 Correct 5 ms 9820 KB Output is correct
10 Correct 5 ms 9816 KB Output is correct
11 Correct 5 ms 10072 KB Output is correct
12 Correct 4 ms 9820 KB Output is correct
13 Correct 4 ms 9820 KB Output is correct
14 Correct 4 ms 9820 KB Output is correct
15 Correct 5 ms 9820 KB Output is correct
16 Correct 4 ms 9820 KB Output is correct
17 Correct 6 ms 10076 KB Output is correct
18 Correct 28 ms 10332 KB Output is correct
19 Correct 47 ms 10328 KB Output is correct
20 Correct 23 ms 10328 KB Output is correct
21 Correct 26 ms 10220 KB Output is correct
22 Correct 47 ms 10328 KB Output is correct
23 Correct 47 ms 10332 KB Output is correct
24 Correct 226 ms 50708 KB Output is correct
25 Execution timed out 10028 ms 57780 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 9816 KB Output is correct
2 Correct 4 ms 9820 KB Output is correct
3 Correct 4 ms 9820 KB Output is correct
4 Correct 4 ms 9820 KB Output is correct
5 Correct 4 ms 9820 KB Output is correct
6 Correct 4 ms 9820 KB Output is correct
7 Correct 4 ms 9652 KB Output is correct
8 Correct 5 ms 9816 KB Output is correct
9 Correct 5 ms 9820 KB Output is correct
10 Correct 5 ms 9816 KB Output is correct
11 Correct 5 ms 10072 KB Output is correct
12 Correct 4 ms 9820 KB Output is correct
13 Correct 4 ms 9820 KB Output is correct
14 Correct 4 ms 9820 KB Output is correct
15 Correct 5 ms 9820 KB Output is correct
16 Correct 4 ms 9820 KB Output is correct
17 Correct 6 ms 10076 KB Output is correct
18 Correct 28 ms 10332 KB Output is correct
19 Correct 47 ms 10328 KB Output is correct
20 Correct 23 ms 10328 KB Output is correct
21 Correct 26 ms 10220 KB Output is correct
22 Correct 47 ms 10328 KB Output is correct
23 Correct 47 ms 10332 KB Output is correct
24 Correct 226 ms 50708 KB Output is correct
25 Execution timed out 10028 ms 57780 KB Time limit exceeded
26 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10015 ms 56796 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10015 ms 56796 KB Time limit exceeded
2 Halted 0 ms 0 KB -