oj.uz

Submission #246869

# Submission time Handle Problem Language Result Execution time Memory
246869 2020-07-10T13:04:11 Z sealnot123 Two Dishes (JOI19_dishes) C++14
82 / 100
 10000 ms 213976 KB 
#include<bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define eb emplace_back
#define all(a) (a).begin(),(a).end()
#define SZ(a) (int)(a).size()
#define FOR(i, a, b) for(int i=(a); i<=(b); ++i)
#define iFOR(i, a, b) for(int i=(a); i>=(b); --i)
#define make_unique(a) sort(all((a))), (a).resize(unique(all((a)))-(a).begin())

using namespace std;

typedef pair<int,int> PII;
typedef long long LL;
typedef double DD;
typedef long double LD;
typedef pair<LL,LL> PLL;
typedef pair<DD,DD> PDD;
typedef vector<int> VI;
typedef vector<LL> VL;

const LL inf = 1e18;
const int N = 1000005;
LL n;
LL seg[N<<2], lazy[N<<2], label[N<<2];
void push_add(int l, int r, int nw){
    if(lazy[nw] == 0) return ;
    seg[nw] += lazy[nw];
    if(l != r){
        lazy[nw<<1] += lazy[nw], lazy[nw<<1|1] += lazy[nw];
    }
    lazy[nw] = 0;
}
void push_label(int l, int r, int nw){
    if(label[nw] == inf) return ;
    seg[nw] = label[nw];
    if(l != r){
        lazy[nw<<1] = lazy[nw<<1|1] = 0;
        label[nw<<1] = label[nw<<1|1] = label[nw];
    }
    label[nw] = inf;
}
void paste(int ll, int rr, LL v, int l = 0, int r = n, int nw = 1){
    push_label(l, r, nw);
    push_add(l, r, nw);
    if(ll > rr || l > rr || r < ll) return ;
    if(l >= ll && r <= rr){
        label[nw] = v;
        push_label(l, r, nw); 
        push_add(l, r, nw);
        return ;
    }
    int m = (l+r)>>1;
    paste(ll, rr, v, l, m, nw<<1);
    paste(ll, rr, v, m+1, r, nw<<1|1);
    seg[nw] = max(seg[nw<<1], seg[nw<<1|1]);
}
void add(int ll, int rr, LL v, int l = 0, int r = n, int nw = 1){
    push_label(l, r, nw);
    push_add(l, r, nw);
    if(l > r || ll > rr || l > rr || r < ll) return ;
    if(l >= ll && r <= rr){
        lazy[nw] = v;
        push_label(l, r, nw);
        push_add(l, r, nw);
        return ;
    }
    int m = (l+r)>>1;
    add(ll, rr, v, l, m, nw<<1);
    add(ll, rr, v, m+1, r, nw<<1|1);
    seg[nw] = max(seg[nw<<1], seg[nw<<1|1]);
}
int search(int ll, int rr, LL v, int l = 0, int r = n, int nw = 1){
    push_label(l, r, nw);
    push_add(l, r, nw);
    if(ll > rr || l > rr || r < ll) return 1<<30;
    if(l == r){
        if(seg[nw] >= v) return l;
        return 1<<30;
    }
    int m = (l+r)>>1;
    if(l >= ll && r <= rr){
        push_label(l, m, nw<<1);
        push_add(l, m, nw<<1);
        if(seg[nw<<1] >= v) return search(ll, rr, v, l, m, nw<<1);
        return search(ll, rr, v, m+1, r, nw<<1|1);
    }
    return min( search(ll, rr, v, l, m, nw<<1), search(ll, rr, v, m+1, r, nw<<1|1));
}
LL get(int idx, int l = 0, int r = n, int nw = 1){
    push_label(l, r, nw);
    push_add(l, r, nw);
    if(l == r) return seg[nw];
    int m = (l+r)>>1;
    if(idx <= m) return get(idx, l, m, nw<<1);
    return get(idx, m+1, r, nw<<1|1);
}

LL A[N], B[N];
LL S[N], T[N];
LL P[N], Q[N];
vector< PLL > sweep[N];
LL m;
void fastscan(LL &x)
{
    bool neg=false;
    register LL c;
    c=getchar();
    if(c=='-')
    {
        neg = true;
        c=getchar();
    }
    for(;(c>47 && c<58);c=getchar())
        x = (x<<1) + (x<<3) +c -48;
    if(neg)
        x *=-1;
} 
int main(){
    fastscan(n); fastscan(m);
    FOR(i, 1, n) fastscan(A[i]), fastscan(S[i]), fastscan(P[i]), A[i] += A[i-1];
    FOR(i, 1, m) fastscan(B[i]), fastscan(T[i]), fastscan(Q[i]), B[i] += B[i-1];
    FOR(i, 1, (n+1)<<2) label[i] = inf;
    FOR(i, 1, n){
        int pA = upper_bound(B, B+1+m, S[i]-A[i]) - B - 1;
        if(pA == -1) continue;
        sweep[pA+1].pb(PLL(i-1, P[i]));
    }
    //seg.print(); puts("");
    FOR(i, 1, m){
        int pB = upper_bound(A, A+1+n, T[i]-B[i]) - A - 1;
        if(pB != -1) add(0, pB, Q[i]), sweep[i].pb( PLL(pB, 0) );
        //printf("#"); seg.print(); puts("");
        sweep[i].pb( PLL(n, 0) );
        sort( all( sweep[i] ) );
        //printf("sweep: "); for(PLL e : sweep[i]) printf("(%lld, %lld) ",e.x,e.y);
        //puts("");
        FOR(j, 0, SZ(sweep[i])-2){
            int now = sweep[i][j].x;
            LL upd = sweep[i][j].y;
            int nxt = sweep[i][j+1].x;
            add(now+1, n, upd);
            // printf("##"); seg.print(); puts("");
            if(now == nxt) continue;
            LL value = get(now);
            int stop_point = search(now+1, nxt, value);
            //printf("j %d (%d, %d) %lld stop = %d\n",j,now,nxt,value,stop_point);
            paste(now+1, min(stop_point-1, nxt), value);
        }
        sweep[i].clear();
        //seg.print(); puts("");
    }
    //puts("");
    for(PLL e : sweep[m+1]) add(e.x+1, n, e.y);
    printf("%lld",get(n));
	return 0;
}
/*
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 674 ms 61816 KB Output is correct
2 Correct 556 ms 62704 KB Output is correct
3 Correct 297 ms 61024 KB Output is correct
4 Correct 526 ms 57424 KB Output is correct
5 Correct 18 ms 23936 KB Output is correct
6 Correct 538 ms 61548 KB Output is correct
7 Correct 135 ms 38392 KB Output is correct
8 Correct 172 ms 47068 KB Output is correct
9 Correct 304 ms 61148 KB Output is correct
10 Correct 539 ms 64248 KB Output is correct
11 Correct 225 ms 61148 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23936 KB Output is correct
2 Correct 18 ms 23808 KB Output is correct
3 Correct 18 ms 23680 KB Output is correct
4 Correct 19 ms 23936 KB Output is correct
5 Correct 18 ms 23808 KB Output is correct
6 Correct 19 ms 23936 KB Output is correct
7 Correct 19 ms 23936 KB Output is correct
8 Correct 19 ms 23808 KB Output is correct
9 Correct 20 ms 23936 KB Output is correct
10 Correct 18 ms 23808 KB Output is correct
11 Correct 18 ms 23808 KB Output is correct
12 Correct 19 ms 23808 KB Output is correct
13 Correct 19 ms 23936 KB Output is correct
14 Correct 19 ms 23808 KB Output is correct
15 Correct 19 ms 23808 KB Output is correct
16 Correct 18 ms 23808 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23936 KB Output is correct
2 Correct 18 ms 23808 KB Output is correct
3 Correct 18 ms 23680 KB Output is correct
4 Correct 19 ms 23936 KB Output is correct
5 Correct 18 ms 23808 KB Output is correct
6 Correct 19 ms 23936 KB Output is correct
7 Correct 19 ms 23936 KB Output is correct
8 Correct 19 ms 23808 KB Output is correct
9 Correct 20 ms 23936 KB Output is correct
10 Correct 18 ms 23808 KB Output is correct
11 Correct 18 ms 23808 KB Output is correct
12 Correct 19 ms 23808 KB Output is correct
13 Correct 19 ms 23936 KB Output is correct
14 Correct 19 ms 23808 KB Output is correct
15 Correct 19 ms 23808 KB Output is correct
16 Correct 18 ms 23808 KB Output is correct
17 Correct 21 ms 24320 KB Output is correct
18 Correct 22 ms 24320 KB Output is correct
19 Correct 25 ms 24320 KB Output is correct
20 Correct 23 ms 24320 KB Output is correct
21 Correct 24 ms 24448 KB Output is correct
22 Correct 25 ms 24320 KB Output is correct
23 Correct 25 ms 24320 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23936 KB Output is correct
2 Correct 18 ms 23808 KB Output is correct
3 Correct 18 ms 23680 KB Output is correct
4 Correct 19 ms 23936 KB Output is correct
5 Correct 18 ms 23808 KB Output is correct
6 Correct 19 ms 23936 KB Output is correct
7 Correct 19 ms 23936 KB Output is correct
8 Correct 19 ms 23808 KB Output is correct
9 Correct 20 ms 23936 KB Output is correct
10 Correct 18 ms 23808 KB Output is correct
11 Correct 18 ms 23808 KB Output is correct
12 Correct 19 ms 23808 KB Output is correct
13 Correct 19 ms 23936 KB Output is correct
14 Correct 19 ms 23808 KB Output is correct
15 Correct 19 ms 23808 KB Output is correct
16 Correct 18 ms 23808 KB Output is correct
17 Correct 21 ms 24320 KB Output is correct
18 Correct 22 ms 24320 KB Output is correct
19 Correct 25 ms 24320 KB Output is correct
20 Correct 23 ms 24320 KB Output is correct
21 Correct 24 ms 24448 KB Output is correct
22 Correct 25 ms 24320 KB Output is correct
23 Correct 25 ms 24320 KB Output is correct
24 Correct 313 ms 59740 KB Output is correct
25 Correct 636 ms 59764 KB Output is correct
26 Correct 442 ms 61432 KB Output is correct
27 Correct 547 ms 59876 KB Output is correct
28 Correct 568 ms 61284 KB Output is correct
29 Correct 266 ms 61272 KB Output is correct
30 Correct 1606 ms 63964 KB Output is correct
31 Correct 128 ms 39032 KB Output is correct
32 Correct 189 ms 47272 KB Output is correct
33 Correct 817 ms 58476 KB Output is correct
34 Correct 1215 ms 62572 KB Output is correct
35 Correct 1461 ms 64124 KB Output is correct
36 Correct 1422 ms 63920 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23936 KB Output is correct
2 Correct 18 ms 23808 KB Output is correct
3 Correct 18 ms 23680 KB Output is correct
4 Correct 19 ms 23936 KB Output is correct
5 Correct 18 ms 23808 KB Output is correct
6 Correct 19 ms 23936 KB Output is correct
7 Correct 19 ms 23936 KB Output is correct
8 Correct 19 ms 23808 KB Output is correct
9 Correct 20 ms 23936 KB Output is correct
10 Correct 18 ms 23808 KB Output is correct
11 Correct 18 ms 23808 KB Output is correct
12 Correct 19 ms 23808 KB Output is correct
13 Correct 19 ms 23936 KB Output is correct
14 Correct 19 ms 23808 KB Output is correct
15 Correct 19 ms 23808 KB Output is correct
16 Correct 18 ms 23808 KB Output is correct
17 Correct 21 ms 24320 KB Output is correct
18 Correct 22 ms 24320 KB Output is correct
19 Correct 25 ms 24320 KB Output is correct
20 Correct 23 ms 24320 KB Output is correct
21 Correct 24 ms 24448 KB Output is correct
22 Correct 25 ms 24320 KB Output is correct
23 Correct 25 ms 24320 KB Output is correct
24 Correct 313 ms 59740 KB Output is correct
25 Correct 636 ms 59764 KB Output is correct
26 Correct 442 ms 61432 KB Output is correct
27 Correct 547 ms 59876 KB Output is correct
28 Correct 568 ms 61284 KB Output is correct
29 Correct 266 ms 61272 KB Output is correct
30 Correct 1606 ms 63964 KB Output is correct
31 Correct 128 ms 39032 KB Output is correct
32 Correct 189 ms 47272 KB Output is correct
33 Correct 817 ms 58476 KB Output is correct
34 Correct 1215 ms 62572 KB Output is correct
35 Correct 1461 ms 64124 KB Output is correct
36 Correct 1422 ms 63920 KB Output is correct
37 Correct 493 ms 61304 KB Output is correct
38 Correct 608 ms 59808 KB Output is correct
39 Correct 660 ms 64504 KB Output is correct
40 Correct 537 ms 64372 KB Output is correct
41 Correct 19 ms 23808 KB Output is correct
42 Correct 1597 ms 64108 KB Output is correct
43 Correct 837 ms 58488 KB Output is correct
44 Correct 1165 ms 62440 KB Output is correct
45 Correct 1539 ms 63980 KB Output is correct

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23936 KB Output is correct
2 Correct 18 ms 23808 KB Output is correct
3 Correct 18 ms 23680 KB Output is correct
4 Correct 19 ms 23936 KB Output is correct
5 Correct 18 ms 23808 KB Output is correct
6 Correct 19 ms 23936 KB Output is correct
7 Correct 19 ms 23936 KB Output is correct
8 Correct 19 ms 23808 KB Output is correct
9 Correct 20 ms 23936 KB Output is correct
10 Correct 18 ms 23808 KB Output is correct
11 Correct 18 ms 23808 KB Output is correct
12 Correct 19 ms 23808 KB Output is correct
13 Correct 19 ms 23936 KB Output is correct
14 Correct 19 ms 23808 KB Output is correct
15 Correct 19 ms 23808 KB Output is correct
16 Correct 18 ms 23808 KB Output is correct
17 Correct 21 ms 24320 KB Output is correct
18 Correct 22 ms 24320 KB Output is correct
19 Correct 25 ms 24320 KB Output is correct
20 Correct 23 ms 24320 KB Output is correct
21 Correct 24 ms 24448 KB Output is correct
22 Correct 25 ms 24320 KB Output is correct
23 Correct 25 ms 24320 KB Output is correct
24 Correct 313 ms 59740 KB Output is correct
25 Correct 636 ms 59764 KB Output is correct
26 Correct 442 ms 61432 KB Output is correct
27 Correct 547 ms 59876 KB Output is correct
28 Correct 568 ms 61284 KB Output is correct
29 Correct 266 ms 61272 KB Output is correct
30 Correct 1606 ms 63964 KB Output is correct
31 Correct 128 ms 39032 KB Output is correct
32 Correct 189 ms 47272 KB Output is correct
33 Correct 817 ms 58476 KB Output is correct
34 Correct 1215 ms 62572 KB Output is correct
35 Correct 1461 ms 64124 KB Output is correct
36 Correct 1422 ms 63920 KB Output is correct
37 Correct 493 ms 61304 KB Output is correct
38 Correct 608 ms 59808 KB Output is correct
39 Correct 660 ms 64504 KB Output is correct
40 Correct 537 ms 64372 KB Output is correct
41 Correct 19 ms 23808 KB Output is correct
42 Correct 1597 ms 64108 KB Output is correct
43 Correct 837 ms 58488 KB Output is correct
44 Correct 1165 ms 62440 KB Output is correct
45 Correct 1539 ms 63980 KB Output is correct
46 Correct 2644 ms 198084 KB Output is correct
47 Correct 3263 ms 190356 KB Output is correct
48 Correct 3858 ms 213976 KB Output is correct
49 Correct 2891 ms 213868 KB Output is correct
50 Execution timed out 10108 ms 202596 KB Time limit exceeded
51 Halted 0 ms 0 KB -

Subtask #7
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 674 ms 61816 KB Output is correct
2 Correct 556 ms 62704 KB Output is correct
3 Correct 297 ms 61024 KB Output is correct
4 Correct 526 ms 57424 KB Output is correct
5 Correct 18 ms 23936 KB Output is correct
6 Correct 538 ms 61548 KB Output is correct
7 Correct 135 ms 38392 KB Output is correct
8 Correct 172 ms 47068 KB Output is correct
9 Correct 304 ms 61148 KB Output is correct
10 Correct 539 ms 64248 KB Output is correct
11 Correct 225 ms 61148 KB Output is correct
12 Correct 18 ms 23936 KB Output is correct
13 Correct 18 ms 23808 KB Output is correct
14 Correct 18 ms 23680 KB Output is correct
15 Correct 19 ms 23936 KB Output is correct
16 Correct 18 ms 23808 KB Output is correct
17 Correct 19 ms 23936 KB Output is correct
18 Correct 19 ms 23936 KB Output is correct
19 Correct 19 ms 23808 KB Output is correct
20 Correct 20 ms 23936 KB Output is correct
21 Correct 18 ms 23808 KB Output is correct
22 Correct 18 ms 23808 KB Output is correct
23 Correct 19 ms 23808 KB Output is correct
24 Correct 19 ms 23936 KB Output is correct
25 Correct 19 ms 23808 KB Output is correct
26 Correct 19 ms 23808 KB Output is correct
27 Correct 18 ms 23808 KB Output is correct
28 Correct 21 ms 24320 KB Output is correct
29 Correct 22 ms 24320 KB Output is correct
30 Correct 25 ms 24320 KB Output is correct
31 Correct 23 ms 24320 KB Output is correct
32 Correct 24 ms 24448 KB Output is correct
33 Correct 25 ms 24320 KB Output is correct
34 Correct 25 ms 24320 KB Output is correct
35 Correct 313 ms 59740 KB Output is correct
36 Correct 636 ms 59764 KB Output is correct
37 Correct 442 ms 61432 KB Output is correct
38 Correct 547 ms 59876 KB Output is correct
39 Correct 568 ms 61284 KB Output is correct
40 Correct 266 ms 61272 KB Output is correct
41 Correct 1606 ms 63964 KB Output is correct
42 Correct 128 ms 39032 KB Output is correct
43 Correct 189 ms 47272 KB Output is correct
44 Correct 817 ms 58476 KB Output is correct
45 Correct 1215 ms 62572 KB Output is correct
46 Correct 1461 ms 64124 KB Output is correct
47 Correct 1422 ms 63920 KB Output is correct
48 Correct 493 ms 61304 KB Output is correct
49 Correct 608 ms 59808 KB Output is correct
50 Correct 660 ms 64504 KB Output is correct
51 Correct 537 ms 64372 KB Output is correct
52 Correct 19 ms 23808 KB Output is correct
53 Correct 1597 ms 64108 KB Output is correct
54 Correct 837 ms 58488 KB Output is correct
55 Correct 1165 ms 62440 KB Output is correct
56 Correct 1539 ms 63980 KB Output is correct
57 Correct 584 ms 60836 KB Output is correct
58 Correct 524 ms 58980 KB Output is correct
59 Correct 543 ms 63736 KB Output is correct
60 Correct 678 ms 63736 KB Output is correct
61 Correct 1283 ms 61164 KB Output is correct
62 Correct 19 ms 23936 KB Output is correct
63 Correct 1570 ms 63236 KB Output is correct
64 Correct 862 ms 57720 KB Output is correct
65 Correct 1150 ms 61808 KB Output is correct
66 Correct 1432 ms 63224 KB Output is correct

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 674 ms 61816 KB Output is correct
2 Correct 556 ms 62704 KB Output is correct
3 Correct 297 ms 61024 KB Output is correct
4 Correct 526 ms 57424 KB Output is correct
5 Correct 18 ms 23936 KB Output is correct
6 Correct 538 ms 61548 KB Output is correct
7 Correct 135 ms 38392 KB Output is correct
8 Correct 172 ms 47068 KB Output is correct
9 Correct 304 ms 61148 KB Output is correct
10 Correct 539 ms 64248 KB Output is correct
11 Correct 225 ms 61148 KB Output is correct
12 Correct 18 ms 23936 KB Output is correct
13 Correct 18 ms 23808 KB Output is correct
14 Correct 18 ms 23680 KB Output is correct
15 Correct 19 ms 23936 KB Output is correct
16 Correct 18 ms 23808 KB Output is correct
17 Correct 19 ms 23936 KB Output is correct
18 Correct 19 ms 23936 KB Output is correct
19 Correct 19 ms 23808 KB Output is correct
20 Correct 20 ms 23936 KB Output is correct
21 Correct 18 ms 23808 KB Output is correct
22 Correct 18 ms 23808 KB Output is correct
23 Correct 19 ms 23808 KB Output is correct
24 Correct 19 ms 23936 KB Output is correct
25 Correct 19 ms 23808 KB Output is correct
26 Correct 19 ms 23808 KB Output is correct
27 Correct 18 ms 23808 KB Output is correct
28 Correct 21 ms 24320 KB Output is correct
29 Correct 22 ms 24320 KB Output is correct
30 Correct 25 ms 24320 KB Output is correct
31 Correct 23 ms 24320 KB Output is correct
32 Correct 24 ms 24448 KB Output is correct
33 Correct 25 ms 24320 KB Output is correct
34 Correct 25 ms 24320 KB Output is correct
35 Correct 313 ms 59740 KB Output is correct
36 Correct 636 ms 59764 KB Output is correct
37 Correct 442 ms 61432 KB Output is correct
38 Correct 547 ms 59876 KB Output is correct
39 Correct 568 ms 61284 KB Output is correct
40 Correct 266 ms 61272 KB Output is correct
41 Correct 1606 ms 63964 KB Output is correct
42 Correct 128 ms 39032 KB Output is correct
43 Correct 189 ms 47272 KB Output is correct
44 Correct 817 ms 58476 KB Output is correct
45 Correct 1215 ms 62572 KB Output is correct
46 Correct 1461 ms 64124 KB Output is correct
47 Correct 1422 ms 63920 KB Output is correct
48 Correct 493 ms 61304 KB Output is correct
49 Correct 608 ms 59808 KB Output is correct
50 Correct 660 ms 64504 KB Output is correct
51 Correct 537 ms 64372 KB Output is correct
52 Correct 19 ms 23808 KB Output is correct
53 Correct 1597 ms 64108 KB Output is correct
54 Correct 837 ms 58488 KB Output is correct
55 Correct 1165 ms 62440 KB Output is correct
56 Correct 1539 ms 63980 KB Output is correct
57 Correct 2644 ms 198084 KB Output is correct
58 Correct 3263 ms 190356 KB Output is correct
59 Correct 3858 ms 213976 KB Output is correct
60 Correct 2891 ms 213868 KB Output is correct
61 Execution timed out 10108 ms 202596 KB Time limit exceeded
62 Halted 0 ms 0 KB -