oj.uz

Submission #246870

# Submission time Handle Problem Language Result Execution time Memory
246870 2020-07-10T13:12:41 Z sealnot123 Two Dishes (JOI19_dishes) C++14
82 / 100
 10000 ms 213488 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(l > rr || r < ll) return rr+1;
    if(l == r){
        if(seg[nw] >= v) return l;
        return rr+1;
    }
    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)-1;
            //printf("j %d (%d, %d) %lld stop = %d\n",j,now,nxt,value,stop_point);
            if(stop_point > now) paste(now+1, stop_point, 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 644 ms 60916 KB Output is correct
2 Correct 593 ms 62080 KB Output is correct
3 Correct 290 ms 60484 KB Output is correct
4 Correct 506 ms 56572 KB Output is correct
5 Correct 24 ms 23808 KB Output is correct
6 Correct 537 ms 61016 KB Output is correct
7 Correct 137 ms 37752 KB Output is correct
8 Correct 169 ms 46556 KB Output is correct
9 Correct 301 ms 60508 KB Output is correct
10 Correct 530 ms 63608 KB Output is correct
11 Correct 219 ms 60380 KB Output is correct

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23936 KB Output is correct
2 Correct 19 ms 23936 KB Output is correct
3 Correct 20 ms 23936 KB Output is correct
4 Correct 18 ms 23808 KB Output is correct
5 Correct 19 ms 23808 KB Output is correct
6 Correct 19 ms 23808 KB Output is correct
7 Correct 18 ms 23808 KB Output is correct
8 Correct 18 ms 23872 KB Output is correct
9 Correct 19 ms 23936 KB Output is correct
10 Correct 19 ms 23808 KB Output is correct
11 Correct 21 ms 23936 KB Output is correct
12 Correct 18 ms 23936 KB Output is correct
13 Correct 19 ms 23936 KB Output is correct
14 Correct 19 ms 23808 KB Output is correct
15 Correct 18 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 19 ms 23936 KB Output is correct
2 Correct 19 ms 23936 KB Output is correct
3 Correct 20 ms 23936 KB Output is correct
4 Correct 18 ms 23808 KB Output is correct
5 Correct 19 ms 23808 KB Output is correct
6 Correct 19 ms 23808 KB Output is correct
7 Correct 18 ms 23808 KB Output is correct
8 Correct 18 ms 23872 KB Output is correct
9 Correct 19 ms 23936 KB Output is correct
10 Correct 19 ms 23808 KB Output is correct
11 Correct 21 ms 23936 KB Output is correct
12 Correct 18 ms 23936 KB Output is correct
13 Correct 19 ms 23936 KB Output is correct
14 Correct 19 ms 23808 KB Output is correct
15 Correct 18 ms 23808 KB Output is correct
16 Correct 18 ms 23808 KB Output is correct
17 Correct 22 ms 24320 KB Output is correct
18 Correct 23 ms 24264 KB Output is correct
19 Correct 27 ms 24320 KB Output is correct
20 Correct 24 ms 24320 KB Output is correct
21 Correct 24 ms 24320 KB Output is correct
22 Correct 25 ms 24320 KB Output is correct
23 Correct 24 ms 24320 KB Output is correct

Subtask #4
39.0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23936 KB Output is correct
2 Correct 19 ms 23936 KB Output is correct
3 Correct 20 ms 23936 KB Output is correct
4 Correct 18 ms 23808 KB Output is correct
5 Correct 19 ms 23808 KB Output is correct
6 Correct 19 ms 23808 KB Output is correct
7 Correct 18 ms 23808 KB Output is correct
8 Correct 18 ms 23872 KB Output is correct
9 Correct 19 ms 23936 KB Output is correct
10 Correct 19 ms 23808 KB Output is correct
11 Correct 21 ms 23936 KB Output is correct
12 Correct 18 ms 23936 KB Output is correct
13 Correct 19 ms 23936 KB Output is correct
14 Correct 19 ms 23808 KB Output is correct
15 Correct 18 ms 23808 KB Output is correct
16 Correct 18 ms 23808 KB Output is correct
17 Correct 22 ms 24320 KB Output is correct
18 Correct 23 ms 24264 KB Output is correct
19 Correct 27 ms 24320 KB Output is correct
20 Correct 24 ms 24320 KB Output is correct
21 Correct 24 ms 24320 KB Output is correct
22 Correct 25 ms 24320 KB Output is correct
23 Correct 24 ms 24320 KB Output is correct
24 Correct 310 ms 58844 KB Output is correct
25 Correct 628 ms 59040 KB Output is correct
26 Correct 493 ms 60556 KB Output is correct
27 Correct 545 ms 58852 KB Output is correct
28 Correct 598 ms 60516 KB Output is correct
29 Correct 263 ms 60384 KB Output is correct
30 Correct 1516 ms 62968 KB Output is correct
31 Correct 130 ms 38136 KB Output is correct
32 Correct 187 ms 46376 KB Output is correct
33 Correct 809 ms 57720 KB Output is correct
34 Correct 1113 ms 61672 KB Output is correct
35 Correct 1534 ms 63088 KB Output is correct
36 Correct 1419 ms 62840 KB Output is correct

Subtask #5
11.0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23936 KB Output is correct
2 Correct 19 ms 23936 KB Output is correct
3 Correct 20 ms 23936 KB Output is correct
4 Correct 18 ms 23808 KB Output is correct
5 Correct 19 ms 23808 KB Output is correct
6 Correct 19 ms 23808 KB Output is correct
7 Correct 18 ms 23808 KB Output is correct
8 Correct 18 ms 23872 KB Output is correct
9 Correct 19 ms 23936 KB Output is correct
10 Correct 19 ms 23808 KB Output is correct
11 Correct 21 ms 23936 KB Output is correct
12 Correct 18 ms 23936 KB Output is correct
13 Correct 19 ms 23936 KB Output is correct
14 Correct 19 ms 23808 KB Output is correct
15 Correct 18 ms 23808 KB Output is correct
16 Correct 18 ms 23808 KB Output is correct
17 Correct 22 ms 24320 KB Output is correct
18 Correct 23 ms 24264 KB Output is correct
19 Correct 27 ms 24320 KB Output is correct
20 Correct 24 ms 24320 KB Output is correct
21 Correct 24 ms 24320 KB Output is correct
22 Correct 25 ms 24320 KB Output is correct
23 Correct 24 ms 24320 KB Output is correct
24 Correct 310 ms 58844 KB Output is correct
25 Correct 628 ms 59040 KB Output is correct
26 Correct 493 ms 60556 KB Output is correct
27 Correct 545 ms 58852 KB Output is correct
28 Correct 598 ms 60516 KB Output is correct
29 Correct 263 ms 60384 KB Output is correct
30 Correct 1516 ms 62968 KB Output is correct
31 Correct 130 ms 38136 KB Output is correct
32 Correct 187 ms 46376 KB Output is correct
33 Correct 809 ms 57720 KB Output is correct
34 Correct 1113 ms 61672 KB Output is correct
35 Correct 1534 ms 63088 KB Output is correct
36 Correct 1419 ms 62840 KB Output is correct
37 Correct 487 ms 60592 KB Output is correct
38 Correct 589 ms 58852 KB Output is correct
39 Correct 669 ms 63608 KB Output is correct
40 Correct 551 ms 63608 KB Output is correct
41 Correct 18 ms 23936 KB Output is correct
42 Correct 1541 ms 62984 KB Output is correct
43 Correct 830 ms 57592 KB Output is correct
44 Correct 1182 ms 61648 KB Output is correct
45 Correct 1614 ms 63224 KB Output is correct

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 23936 KB Output is correct
2 Correct 19 ms 23936 KB Output is correct
3 Correct 20 ms 23936 KB Output is correct
4 Correct 18 ms 23808 KB Output is correct
5 Correct 19 ms 23808 KB Output is correct
6 Correct 19 ms 23808 KB Output is correct
7 Correct 18 ms 23808 KB Output is correct
8 Correct 18 ms 23872 KB Output is correct
9 Correct 19 ms 23936 KB Output is correct
10 Correct 19 ms 23808 KB Output is correct
11 Correct 21 ms 23936 KB Output is correct
12 Correct 18 ms 23936 KB Output is correct
13 Correct 19 ms 23936 KB Output is correct
14 Correct 19 ms 23808 KB Output is correct
15 Correct 18 ms 23808 KB Output is correct
16 Correct 18 ms 23808 KB Output is correct
17 Correct 22 ms 24320 KB Output is correct
18 Correct 23 ms 24264 KB Output is correct
19 Correct 27 ms 24320 KB Output is correct
20 Correct 24 ms 24320 KB Output is correct
21 Correct 24 ms 24320 KB Output is correct
22 Correct 25 ms 24320 KB Output is correct
23 Correct 24 ms 24320 KB Output is correct
24 Correct 310 ms 58844 KB Output is correct
25 Correct 628 ms 59040 KB Output is correct
26 Correct 493 ms 60556 KB Output is correct
27 Correct 545 ms 58852 KB Output is correct
28 Correct 598 ms 60516 KB Output is correct
29 Correct 263 ms 60384 KB Output is correct
30 Correct 1516 ms 62968 KB Output is correct
31 Correct 130 ms 38136 KB Output is correct
32 Correct 187 ms 46376 KB Output is correct
33 Correct 809 ms 57720 KB Output is correct
34 Correct 1113 ms 61672 KB Output is correct
35 Correct 1534 ms 63088 KB Output is correct
36 Correct 1419 ms 62840 KB Output is correct
37 Correct 487 ms 60592 KB Output is correct
38 Correct 589 ms 58852 KB Output is correct
39 Correct 669 ms 63608 KB Output is correct
40 Correct 551 ms 63608 KB Output is correct
41 Correct 18 ms 23936 KB Output is correct
42 Correct 1541 ms 62984 KB Output is correct
43 Correct 830 ms 57592 KB Output is correct
44 Correct 1182 ms 61648 KB Output is correct
45 Correct 1614 ms 63224 KB Output is correct
46 Correct 2443 ms 197624 KB Output is correct
47 Correct 3179 ms 190036 KB Output is correct
48 Correct 4053 ms 213376 KB Output is correct
49 Correct 2889 ms 213488 KB Output is correct
50 Execution timed out 10034 ms 203512 KB Time limit exceeded
51 Halted 0 ms 0 KB -

Subtask #7
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 644 ms 60916 KB Output is correct
2 Correct 593 ms 62080 KB Output is correct
3 Correct 290 ms 60484 KB Output is correct
4 Correct 506 ms 56572 KB Output is correct
5 Correct 24 ms 23808 KB Output is correct
6 Correct 537 ms 61016 KB Output is correct
7 Correct 137 ms 37752 KB Output is correct
8 Correct 169 ms 46556 KB Output is correct
9 Correct 301 ms 60508 KB Output is correct
10 Correct 530 ms 63608 KB Output is correct
11 Correct 219 ms 60380 KB Output is correct
12 Correct 19 ms 23936 KB Output is correct
13 Correct 19 ms 23936 KB Output is correct
14 Correct 20 ms 23936 KB Output is correct
15 Correct 18 ms 23808 KB Output is correct
16 Correct 19 ms 23808 KB Output is correct
17 Correct 19 ms 23808 KB Output is correct
18 Correct 18 ms 23808 KB Output is correct
19 Correct 18 ms 23872 KB Output is correct
20 Correct 19 ms 23936 KB Output is correct
21 Correct 19 ms 23808 KB Output is correct
22 Correct 21 ms 23936 KB Output is correct
23 Correct 18 ms 23936 KB Output is correct
24 Correct 19 ms 23936 KB Output is correct
25 Correct 19 ms 23808 KB Output is correct
26 Correct 18 ms 23808 KB Output is correct
27 Correct 18 ms 23808 KB Output is correct
28 Correct 22 ms 24320 KB Output is correct
29 Correct 23 ms 24264 KB Output is correct
30 Correct 27 ms 24320 KB Output is correct
31 Correct 24 ms 24320 KB Output is correct
32 Correct 24 ms 24320 KB Output is correct
33 Correct 25 ms 24320 KB Output is correct
34 Correct 24 ms 24320 KB Output is correct
35 Correct 310 ms 58844 KB Output is correct
36 Correct 628 ms 59040 KB Output is correct
37 Correct 493 ms 60556 KB Output is correct
38 Correct 545 ms 58852 KB Output is correct
39 Correct 598 ms 60516 KB Output is correct
40 Correct 263 ms 60384 KB Output is correct
41 Correct 1516 ms 62968 KB Output is correct
42 Correct 130 ms 38136 KB Output is correct
43 Correct 187 ms 46376 KB Output is correct
44 Correct 809 ms 57720 KB Output is correct
45 Correct 1113 ms 61672 KB Output is correct
46 Correct 1534 ms 63088 KB Output is correct
47 Correct 1419 ms 62840 KB Output is correct
48 Correct 487 ms 60592 KB Output is correct
49 Correct 589 ms 58852 KB Output is correct
50 Correct 669 ms 63608 KB Output is correct
51 Correct 551 ms 63608 KB Output is correct
52 Correct 18 ms 23936 KB Output is correct
53 Correct 1541 ms 62984 KB Output is correct
54 Correct 830 ms 57592 KB Output is correct
55 Correct 1182 ms 61648 KB Output is correct
56 Correct 1614 ms 63224 KB Output is correct
57 Correct 576 ms 60548 KB Output is correct
58 Correct 543 ms 59176 KB Output is correct
59 Correct 546 ms 63736 KB Output is correct
60 Correct 643 ms 63608 KB Output is correct
61 Correct 1308 ms 61144 KB Output is correct
62 Correct 19 ms 23808 KB Output is correct
63 Correct 1620 ms 63048 KB Output is correct
64 Correct 843 ms 57592 KB Output is correct
65 Correct 1147 ms 61936 KB Output is correct
66 Correct 1427 ms 63084 KB Output is correct

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 644 ms 60916 KB Output is correct
2 Correct 593 ms 62080 KB Output is correct
3 Correct 290 ms 60484 KB Output is correct
4 Correct 506 ms 56572 KB Output is correct
5 Correct 24 ms 23808 KB Output is correct
6 Correct 537 ms 61016 KB Output is correct
7 Correct 137 ms 37752 KB Output is correct
8 Correct 169 ms 46556 KB Output is correct
9 Correct 301 ms 60508 KB Output is correct
10 Correct 530 ms 63608 KB Output is correct
11 Correct 219 ms 60380 KB Output is correct
12 Correct 19 ms 23936 KB Output is correct
13 Correct 19 ms 23936 KB Output is correct
14 Correct 20 ms 23936 KB Output is correct
15 Correct 18 ms 23808 KB Output is correct
16 Correct 19 ms 23808 KB Output is correct
17 Correct 19 ms 23808 KB Output is correct
18 Correct 18 ms 23808 KB Output is correct
19 Correct 18 ms 23872 KB Output is correct
20 Correct 19 ms 23936 KB Output is correct
21 Correct 19 ms 23808 KB Output is correct
22 Correct 21 ms 23936 KB Output is correct
23 Correct 18 ms 23936 KB Output is correct
24 Correct 19 ms 23936 KB Output is correct
25 Correct 19 ms 23808 KB Output is correct
26 Correct 18 ms 23808 KB Output is correct
27 Correct 18 ms 23808 KB Output is correct
28 Correct 22 ms 24320 KB Output is correct
29 Correct 23 ms 24264 KB Output is correct
30 Correct 27 ms 24320 KB Output is correct
31 Correct 24 ms 24320 KB Output is correct
32 Correct 24 ms 24320 KB Output is correct
33 Correct 25 ms 24320 KB Output is correct
34 Correct 24 ms 24320 KB Output is correct
35 Correct 310 ms 58844 KB Output is correct
36 Correct 628 ms 59040 KB Output is correct
37 Correct 493 ms 60556 KB Output is correct
38 Correct 545 ms 58852 KB Output is correct
39 Correct 598 ms 60516 KB Output is correct
40 Correct 263 ms 60384 KB Output is correct
41 Correct 1516 ms 62968 KB Output is correct
42 Correct 130 ms 38136 KB Output is correct
43 Correct 187 ms 46376 KB Output is correct
44 Correct 809 ms 57720 KB Output is correct
45 Correct 1113 ms 61672 KB Output is correct
46 Correct 1534 ms 63088 KB Output is correct
47 Correct 1419 ms 62840 KB Output is correct
48 Correct 487 ms 60592 KB Output is correct
49 Correct 589 ms 58852 KB Output is correct
50 Correct 669 ms 63608 KB Output is correct
51 Correct 551 ms 63608 KB Output is correct
52 Correct 18 ms 23936 KB Output is correct
53 Correct 1541 ms 62984 KB Output is correct
54 Correct 830 ms 57592 KB Output is correct
55 Correct 1182 ms 61648 KB Output is correct
56 Correct 1614 ms 63224 KB Output is correct
57 Correct 2443 ms 197624 KB Output is correct
58 Correct 3179 ms 190036 KB Output is correct
59 Correct 4053 ms 213376 KB Output is correct
60 Correct 2889 ms 213488 KB Output is correct
61 Execution timed out 10034 ms 203512 KB Time limit exceeded
62 Halted 0 ms 0 KB -