답안 #104740

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
104740	2019-04-09T03:57:41 Z	minhtung0404	Two Dishes (JOI19_dishes)	C++17	100 / 100	8018 ms	87508 KB

dishes

//https://oj.uz/problem/view/JOI19_dishes

#include<bits/stdc++.h>
const int N = 1e6 + 5;
using namespace std;

int n, m, per[N], p[N], q[N];
long long S, sum[N << 2], maxsum[N << 2], a[N], b[N], s[N], t[N];
bool lazy[N << 2];

void dolazy(int i, int l, int r){
    if (!lazy[i]) return;
    if (l != r){
        lazy[i << 1] = lazy[i << 1 | 1] = 1;
    }
    sum[i] = maxsum[i] = lazy[i] = 0;
}

void update(int i, int l, int r, int L, int R){
    dolazy(i, l, r);
    if (L > r || l > R || L > R) return;
    if (L <= l && r <= R){
        lazy[i] = 1;
        dolazy(i, l, r);
        return;
    }
    int mid = (l + r) >> 1;
    update(i << 1, l, mid, L, R); update(i << 1 | 1, mid+1, r, L, R);
    sum[i] = sum[i << 1] + sum[i << 1 | 1];
    maxsum[i] = max(maxsum[i << 1], sum[i << 1] + maxsum[i << 1 | 1]);
}

void update_pos(int i, int l, int r, int pos, long long val){
    dolazy(i, l, r);
    if (l > pos || pos > r) return;
    if (l == r){
        sum[i] += val;
        maxsum[i] += val;
        return;
    }
    int mid = (l + r) >> 1;
    update_pos(i << 1, l, mid, pos, val); update_pos(i << 1 | 1, mid+1, r, pos, val);
    sum[i] = sum[i << 1] + sum[i << 1 | 1];
    maxsum[i] = max(maxsum[i << 1], sum[i << 1] + maxsum[i << 1 | 1]);
}

long long get(int i, int l, int r, int L, int R){
    dolazy(i, l, r);
    if (L > r || l > R || L > R) return 0;
    if (L <= l && r <= R) return sum[i];
    int mid = (l + r) >> 1;
    return get(i << 1, l, mid, L, R) + get(i << 1 | 1, mid+1, r, L, R);
}

int Find(int i, int l, int r, int pos, long long k){
    dolazy(i, l, r);
    if (r < pos || maxsum[i] < k) return n+1;
    if (l == r) return l;
    int mid = (l + r) >> 1;
    int ans = Find(i << 1, l, mid, pos, k);
    if (ans == n+1) ans = Find(i << 1 | 1, mid+1, r, pos, k - sum[i << 1]);
    return ans;
}

void change(int pos){
    int x = Find(1, 1, n, pos, get(1, 1, n, 1, pos-1));
    if (x == pos) return;
    if (x <= n) update_pos(1, 1, n, x, get(1, 1, n, pos, x-1));
    update(1, 1, n, pos, x-1);
}

signed main(){
    ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for (int i = 1; i <= n; i++) cin >> a[i] >> s[i] >> p[i], a[i] += a[i-1], s[i] -= a[i], per[i] = i;
    for (int i = 1; i <= m; i++) cin >> b[i] >> t[i] >> q[i], b[i] += b[i-1], t[i] -= b[i];
    sort(per+1, per+1+n, [](int x, int y){return s[x] < s[y];});
    int cnt = 1;
    while (cnt <= n && s[per[cnt]] < 0) p[per[cnt++]] = 0;
    for (int i = 1; i <= m; i++){
        vector <int> mv;
        while (cnt <= n && s[per[cnt]] < b[i]){
            int id = per[cnt++];
            update_pos(1, 1, n, id, p[id]); p[id] = 0;
            mv.push_back(id);
        }
        if (t[i] >= 0) {
            int l = 0, r = n;
            while (l != r){
                int mid = (l + r + 1) >> 1;
                if (a[mid] <= t[i]) l = mid;
                else r = mid-1;
            }
            S += q[i];
            if (l != n){
                update_pos(1, 1, n, l+1, -q[i]);
                mv.push_back(l+1);
            }
        }
        sort(mv.begin(), mv.end());
        for (auto id : mv) change(id);
    }
    long long ans = S + sum[1];
    for (int i = 1; i <= n; i++) ans += p[i];
    cout << ans;
}

Subtask #1
5.0 / 5.0

#	결과	실행 시간	메모리	Grader output
1	Correct	430 ms	17016 KB	Output is correct
2	Correct	430 ms	16804 KB	Output is correct
3	Correct	192 ms	9132 KB	Output is correct
4	Correct	433 ms	14596 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	450 ms	15196 KB	Output is correct
7	Correct	104 ms	4328 KB	Output is correct
8	Correct	124 ms	5164 KB	Output is correct
9	Correct	201 ms	9080 KB	Output is correct
10	Correct	512 ms	17876 KB	Output is correct
11	Correct	145 ms	9048 KB	Output is correct

Subtask #2
3.0 / 3.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	3 ms	384 KB	Output is correct
6	Correct	3 ms	384 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	2 ms	384 KB	Output is correct
12	Correct	2 ms	384 KB	Output is correct
13	Correct	2 ms	384 KB	Output is correct
14	Correct	3 ms	384 KB	Output is correct
15	Correct	2 ms	384 KB	Output is correct
16	Correct	2 ms	512 KB	Output is correct

Subtask #3
7.0 / 7.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	3 ms	384 KB	Output is correct
6	Correct	3 ms	384 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	2 ms	384 KB	Output is correct
12	Correct	2 ms	384 KB	Output is correct
13	Correct	2 ms	384 KB	Output is correct
14	Correct	3 ms	384 KB	Output is correct
15	Correct	2 ms	384 KB	Output is correct
16	Correct	2 ms	512 KB	Output is correct
17	Correct	4 ms	640 KB	Output is correct
18	Correct	4 ms	512 KB	Output is correct
19	Correct	8 ms	640 KB	Output is correct
20	Correct	5 ms	640 KB	Output is correct
21	Correct	6 ms	512 KB	Output is correct
22	Correct	9 ms	640 KB	Output is correct
23	Correct	10 ms	640 KB	Output is correct

Subtask #4
39.0 / 39.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	3 ms	384 KB	Output is correct
6	Correct	3 ms	384 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	2 ms	384 KB	Output is correct
12	Correct	2 ms	384 KB	Output is correct
13	Correct	2 ms	384 KB	Output is correct
14	Correct	3 ms	384 KB	Output is correct
15	Correct	2 ms	384 KB	Output is correct
16	Correct	2 ms	512 KB	Output is correct
17	Correct	4 ms	640 KB	Output is correct
18	Correct	4 ms	512 KB	Output is correct
19	Correct	8 ms	640 KB	Output is correct
20	Correct	5 ms	640 KB	Output is correct
21	Correct	6 ms	512 KB	Output is correct
22	Correct	9 ms	640 KB	Output is correct
23	Correct	10 ms	640 KB	Output is correct
24	Correct	452 ms	18460 KB	Output is correct
25	Correct	404 ms	9336 KB	Output is correct
26	Correct	277 ms	17272 KB	Output is correct
27	Correct	382 ms	17928 KB	Output is correct
28	Correct	505 ms	17892 KB	Output is correct
29	Correct	196 ms	9080 KB	Output is correct
30	Correct	1243 ms	17844 KB	Output is correct
31	Correct	91 ms	4344 KB	Output is correct
32	Correct	220 ms	13916 KB	Output is correct
33	Correct	728 ms	17716 KB	Output is correct
34	Correct	732 ms	17476 KB	Output is correct
35	Correct	1105 ms	17896 KB	Output is correct
36	Correct	991 ms	17912 KB	Output is correct

Subtask #5
11.0 / 11.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	3 ms	384 KB	Output is correct
6	Correct	3 ms	384 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	2 ms	384 KB	Output is correct
12	Correct	2 ms	384 KB	Output is correct
13	Correct	2 ms	384 KB	Output is correct
14	Correct	3 ms	384 KB	Output is correct
15	Correct	2 ms	384 KB	Output is correct
16	Correct	2 ms	512 KB	Output is correct
17	Correct	4 ms	640 KB	Output is correct
18	Correct	4 ms	512 KB	Output is correct
19	Correct	8 ms	640 KB	Output is correct
20	Correct	5 ms	640 KB	Output is correct
21	Correct	6 ms	512 KB	Output is correct
22	Correct	9 ms	640 KB	Output is correct
23	Correct	10 ms	640 KB	Output is correct
24	Correct	452 ms	18460 KB	Output is correct
25	Correct	404 ms	9336 KB	Output is correct
26	Correct	277 ms	17272 KB	Output is correct
27	Correct	382 ms	17928 KB	Output is correct
28	Correct	505 ms	17892 KB	Output is correct
29	Correct	196 ms	9080 KB	Output is correct
30	Correct	1243 ms	17844 KB	Output is correct
31	Correct	91 ms	4344 KB	Output is correct
32	Correct	220 ms	13916 KB	Output is correct
33	Correct	728 ms	17716 KB	Output is correct
34	Correct	732 ms	17476 KB	Output is correct
35	Correct	1105 ms	17896 KB	Output is correct
36	Correct	991 ms	17912 KB	Output is correct
37	Correct	343 ms	17168 KB	Output is correct
38	Correct	394 ms	17756 KB	Output is correct
39	Correct	879 ms	17808 KB	Output is correct
40	Correct	483 ms	17272 KB	Output is correct
41	Correct	2 ms	384 KB	Output is correct
42	Correct	1174 ms	17788 KB	Output is correct
43	Correct	758 ms	17648 KB	Output is correct
44	Correct	915 ms	17356 KB	Output is correct
45	Correct	1122 ms	17788 KB	Output is correct

Subtask #6
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	2 ms	384 KB	Output is correct
2	Correct	2 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	2 ms	384 KB	Output is correct
5	Correct	3 ms	384 KB	Output is correct
6	Correct	3 ms	384 KB	Output is correct
7	Correct	2 ms	384 KB	Output is correct
8	Correct	2 ms	384 KB	Output is correct
9	Correct	2 ms	384 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	2 ms	384 KB	Output is correct
12	Correct	2 ms	384 KB	Output is correct
13	Correct	2 ms	384 KB	Output is correct
14	Correct	3 ms	384 KB	Output is correct
15	Correct	2 ms	384 KB	Output is correct
16	Correct	2 ms	512 KB	Output is correct
17	Correct	4 ms	640 KB	Output is correct
18	Correct	4 ms	512 KB	Output is correct
19	Correct	8 ms	640 KB	Output is correct
20	Correct	5 ms	640 KB	Output is correct
21	Correct	6 ms	512 KB	Output is correct
22	Correct	9 ms	640 KB	Output is correct
23	Correct	10 ms	640 KB	Output is correct
24	Correct	452 ms	18460 KB	Output is correct
25	Correct	404 ms	9336 KB	Output is correct
26	Correct	277 ms	17272 KB	Output is correct
27	Correct	382 ms	17928 KB	Output is correct
28	Correct	505 ms	17892 KB	Output is correct
29	Correct	196 ms	9080 KB	Output is correct
30	Correct	1243 ms	17844 KB	Output is correct
31	Correct	91 ms	4344 KB	Output is correct
32	Correct	220 ms	13916 KB	Output is correct
33	Correct	728 ms	17716 KB	Output is correct
34	Correct	732 ms	17476 KB	Output is correct
35	Correct	1105 ms	17896 KB	Output is correct
36	Correct	991 ms	17912 KB	Output is correct
37	Correct	343 ms	17168 KB	Output is correct
38	Correct	394 ms	17756 KB	Output is correct
39	Correct	879 ms	17808 KB	Output is correct
40	Correct	483 ms	17272 KB	Output is correct
41	Correct	2 ms	384 KB	Output is correct
42	Correct	1174 ms	17788 KB	Output is correct
43	Correct	758 ms	17648 KB	Output is correct
44	Correct	915 ms	17356 KB	Output is correct
45	Correct	1122 ms	17788 KB	Output is correct
46	Correct	1706 ms	76212 KB	Output is correct
47	Correct	2262 ms	78324 KB	Output is correct
48	Correct	3798 ms	78396 KB	Output is correct
49	Correct	2426 ms	76460 KB	Output is correct
50	Correct	7870 ms	78348 KB	Output is correct
51	Correct	4513 ms	76840 KB	Output is correct
52	Correct	4835 ms	75136 KB	Output is correct
53	Correct	7380 ms	78364 KB	Output is correct

Subtask #7
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	430 ms	17016 KB	Output is correct
2	Correct	430 ms	16804 KB	Output is correct
3	Correct	192 ms	9132 KB	Output is correct
4	Correct	433 ms	14596 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	450 ms	15196 KB	Output is correct
7	Correct	104 ms	4328 KB	Output is correct
8	Correct	124 ms	5164 KB	Output is correct
9	Correct	201 ms	9080 KB	Output is correct
10	Correct	512 ms	17876 KB	Output is correct
11	Correct	145 ms	9048 KB	Output is correct
12	Correct	2 ms	384 KB	Output is correct
13	Correct	2 ms	384 KB	Output is correct
14	Correct	2 ms	384 KB	Output is correct
15	Correct	2 ms	384 KB	Output is correct
16	Correct	3 ms	384 KB	Output is correct
17	Correct	3 ms	384 KB	Output is correct
18	Correct	2 ms	384 KB	Output is correct
19	Correct	2 ms	384 KB	Output is correct
20	Correct	2 ms	384 KB	Output is correct
21	Correct	2 ms	384 KB	Output is correct
22	Correct	2 ms	384 KB	Output is correct
23	Correct	2 ms	384 KB	Output is correct
24	Correct	2 ms	384 KB	Output is correct
25	Correct	3 ms	384 KB	Output is correct
26	Correct	2 ms	384 KB	Output is correct
27	Correct	2 ms	512 KB	Output is correct
28	Correct	4 ms	640 KB	Output is correct
29	Correct	4 ms	512 KB	Output is correct
30	Correct	8 ms	640 KB	Output is correct
31	Correct	5 ms	640 KB	Output is correct
32	Correct	6 ms	512 KB	Output is correct
33	Correct	9 ms	640 KB	Output is correct
34	Correct	10 ms	640 KB	Output is correct
35	Correct	452 ms	18460 KB	Output is correct
36	Correct	404 ms	9336 KB	Output is correct
37	Correct	277 ms	17272 KB	Output is correct
38	Correct	382 ms	17928 KB	Output is correct
39	Correct	505 ms	17892 KB	Output is correct
40	Correct	196 ms	9080 KB	Output is correct
41	Correct	1243 ms	17844 KB	Output is correct
42	Correct	91 ms	4344 KB	Output is correct
43	Correct	220 ms	13916 KB	Output is correct
44	Correct	728 ms	17716 KB	Output is correct
45	Correct	732 ms	17476 KB	Output is correct
46	Correct	1105 ms	17896 KB	Output is correct
47	Correct	991 ms	17912 KB	Output is correct
48	Correct	343 ms	17168 KB	Output is correct
49	Correct	394 ms	17756 KB	Output is correct
50	Correct	879 ms	17808 KB	Output is correct
51	Correct	483 ms	17272 KB	Output is correct
52	Correct	2 ms	384 KB	Output is correct
53	Correct	1174 ms	17788 KB	Output is correct
54	Correct	758 ms	17648 KB	Output is correct
55	Correct	915 ms	17356 KB	Output is correct
56	Correct	1122 ms	17788 KB	Output is correct
57	Correct	380 ms	17756 KB	Output is correct
58	Correct	420 ms	17260 KB	Output is correct
59	Correct	422 ms	17220 KB	Output is correct
60	Correct	678 ms	26800 KB	Output is correct
61	Correct	797 ms	26744 KB	Output is correct
62	Correct	2 ms	384 KB	Output is correct
63	Correct	1229 ms	26620 KB	Output is correct
64	Correct	841 ms	26644 KB	Output is correct
65	Correct	982 ms	26488 KB	Output is correct
66	Correct	1230 ms	25360 KB	Output is correct

Subtask #8
9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	430 ms	17016 KB	Output is correct
2	Correct	430 ms	16804 KB	Output is correct
3	Correct	192 ms	9132 KB	Output is correct
4	Correct	433 ms	14596 KB	Output is correct
5	Correct	2 ms	384 KB	Output is correct
6	Correct	450 ms	15196 KB	Output is correct
7	Correct	104 ms	4328 KB	Output is correct
8	Correct	124 ms	5164 KB	Output is correct
9	Correct	201 ms	9080 KB	Output is correct
10	Correct	512 ms	17876 KB	Output is correct
11	Correct	145 ms	9048 KB	Output is correct
12	Correct	2 ms	384 KB	Output is correct
13	Correct	2 ms	384 KB	Output is correct
14	Correct	2 ms	384 KB	Output is correct
15	Correct	2 ms	384 KB	Output is correct
16	Correct	3 ms	384 KB	Output is correct
17	Correct	3 ms	384 KB	Output is correct
18	Correct	2 ms	384 KB	Output is correct
19	Correct	2 ms	384 KB	Output is correct
20	Correct	2 ms	384 KB	Output is correct
21	Correct	2 ms	384 KB	Output is correct
22	Correct	2 ms	384 KB	Output is correct
23	Correct	2 ms	384 KB	Output is correct
24	Correct	2 ms	384 KB	Output is correct
25	Correct	3 ms	384 KB	Output is correct
26	Correct	2 ms	384 KB	Output is correct
27	Correct	2 ms	512 KB	Output is correct
28	Correct	4 ms	640 KB	Output is correct
29	Correct	4 ms	512 KB	Output is correct
30	Correct	8 ms	640 KB	Output is correct
31	Correct	5 ms	640 KB	Output is correct
32	Correct	6 ms	512 KB	Output is correct
33	Correct	9 ms	640 KB	Output is correct
34	Correct	10 ms	640 KB	Output is correct
35	Correct	452 ms	18460 KB	Output is correct
36	Correct	404 ms	9336 KB	Output is correct
37	Correct	277 ms	17272 KB	Output is correct
38	Correct	382 ms	17928 KB	Output is correct
39	Correct	505 ms	17892 KB	Output is correct
40	Correct	196 ms	9080 KB	Output is correct
41	Correct	1243 ms	17844 KB	Output is correct
42	Correct	91 ms	4344 KB	Output is correct
43	Correct	220 ms	13916 KB	Output is correct
44	Correct	728 ms	17716 KB	Output is correct
45	Correct	732 ms	17476 KB	Output is correct
46	Correct	1105 ms	17896 KB	Output is correct
47	Correct	991 ms	17912 KB	Output is correct
48	Correct	343 ms	17168 KB	Output is correct
49	Correct	394 ms	17756 KB	Output is correct
50	Correct	879 ms	17808 KB	Output is correct
51	Correct	483 ms	17272 KB	Output is correct
52	Correct	2 ms	384 KB	Output is correct
53	Correct	1174 ms	17788 KB	Output is correct
54	Correct	758 ms	17648 KB	Output is correct
55	Correct	915 ms	17356 KB	Output is correct
56	Correct	1122 ms	17788 KB	Output is correct
57	Correct	1706 ms	76212 KB	Output is correct
58	Correct	2262 ms	78324 KB	Output is correct
59	Correct	3798 ms	78396 KB	Output is correct
60	Correct	2426 ms	76460 KB	Output is correct
61	Correct	7870 ms	78348 KB	Output is correct
62	Correct	4513 ms	76840 KB	Output is correct
63	Correct	4835 ms	75136 KB	Output is correct
64	Correct	7380 ms	78364 KB	Output is correct
65	Correct	380 ms	17756 KB	Output is correct
66	Correct	420 ms	17260 KB	Output is correct
67	Correct	422 ms	17220 KB	Output is correct
68	Correct	678 ms	26800 KB	Output is correct
69	Correct	797 ms	26744 KB	Output is correct
70	Correct	2 ms	384 KB	Output is correct
71	Correct	1229 ms	26620 KB	Output is correct
72	Correct	841 ms	26644 KB	Output is correct
73	Correct	982 ms	26488 KB	Output is correct
74	Correct	1230 ms	25360 KB	Output is correct
75	Correct	1937 ms	87508 KB	Output is correct
76	Correct	1942 ms	85236 KB	Output is correct
77	Correct	2385 ms	83696 KB	Output is correct
78	Correct	3488 ms	85444 KB	Output is correct
79	Correct	8018 ms	87156 KB	Output is correct
80	Correct	4632 ms	85240 KB	Output is correct
81	Correct	5483 ms	77888 KB	Output is correct
82	Correct	7658 ms	82924 KB	Output is correct
83	Correct	7839 ms	80120 KB	Output is correct

답안 #104740

Compilation message