oj.uz

Submission #246795

# Submission time Handle Problem Language Result Execution time Memory
246795 2020-07-10T09:26:28 Z sealnot123 Two Dishes (JOI19_dishes) C++14
0 / 100
 10000 ms 53008 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;
int n;
struct segtree{
    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 push(int l, int r, int nw){
        push_label(l, r, nw);
        push_add(l, r, nw);
    }
    void paste(int ll, int rr, LL v, int l = 0, int r = n, int nw = 1){
        push(l, r, nw);
        if(ll > rr || l > rr || r < ll) return ;
        if(l >= ll && r <= rr){
            label[nw] = v;
            push(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(l, r, nw);
        if(ll > rr || l > rr || r < ll) return ;
        if(l >= ll && r <= rr){
            lazy[nw] = v;
            push(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(l, r, nw);
        if(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){
            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(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);
    }
    void print(int l = 0, int r = n, int nw = 1){
        push(l, r, nw);
        if(l == r){
            printf("%lld ",seg[nw]); return ;
        }
        int m = (l+r)>>1;
        print(l, m, nw<<1); print(m+1, r, nw<<1|1);
    }
}seg;

LL A[N], B[N];
LL S[N], T[N];
LL P[N], Q[N];
vector< PLL > sweep[N];

int main(){
    int m;
    scanf("%d %d",&n,&m);
    FOR(i, 1, n) scanf("%lld %lld %lld",&A[i],&S[i],&P[i]), A[i] += A[i-1];
    FOR(i, 1, m) scanf("%lld %lld %lld",&B[i],&T[i],&Q[i]), B[i] += B[i-1];
    FOR(i, 1, n<<2) seg.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) seg.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;
            seg.add(now+1, n, upd);
            // printf("##"); seg.print(); puts("");
            if(now == nxt) continue;
            LL value = seg.get(now);
            int stop_point = seg.search(now+1, nxt, value);
            // printf("j %d (%d, %d) %lld stop = %d\n",j,now,nxt,value,stop_point);
            seg.paste(now+1, min(stop_point-1, nxt), value);
        }
        //seg.print(); puts("");
        FOR(j, 1, n) assert(seg.get(j) >= seg.get(j-1));
    }
    for(PLL e : sweep[m+1]) seg.add(e.x+1, n, e.y);
    printf("%lld",seg.get(n));
	return 0;
}
/*
 *
 *
 *
 *
 *
 *
 *
 *
 *
 *
 */

Compilation message

dishes.cpp: In function 'int main()':
dishes.cpp:111:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d %d",&n,&m);
     ~~~~~^~~~~~~~~~~~~~~
dishes.cpp:112:59: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     FOR(i, 1, n) scanf("%lld %lld %lld",&A[i],&S[i],&P[i]), A[i] += A[i-1];
                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~
dishes.cpp:113:59: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     FOR(i, 1, m) scanf("%lld %lld %lld",&B[i],&T[i],&Q[i]), B[i] += B[i-1];
                  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 19 ms 23984 KB Output is correct
3 Correct 19 ms 23936 KB Output is correct
4 Correct 19 ms 23808 KB Output is correct
5 Correct 18 ms 23928 KB Output is correct
6 Correct 18 ms 23808 KB Output is correct
7 Correct 18 ms 23936 KB Output is correct
8 Correct 18 ms 23808 KB Output is correct
9 Correct 19 ms 23936 KB Output is correct
10 Incorrect 19 ms 23808 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 19 ms 23984 KB Output is correct
3 Correct 19 ms 23936 KB Output is correct
4 Correct 19 ms 23808 KB Output is correct
5 Correct 18 ms 23928 KB Output is correct
6 Correct 18 ms 23808 KB Output is correct
7 Correct 18 ms 23936 KB Output is correct
8 Correct 18 ms 23808 KB Output is correct
9 Correct 19 ms 23936 KB Output is correct
10 Incorrect 19 ms 23808 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 19 ms 23984 KB Output is correct
3 Correct 19 ms 23936 KB Output is correct
4 Correct 19 ms 23808 KB Output is correct
5 Correct 18 ms 23928 KB Output is correct
6 Correct 18 ms 23808 KB Output is correct
7 Correct 18 ms 23936 KB Output is correct
8 Correct 18 ms 23808 KB Output is correct
9 Correct 19 ms 23936 KB Output is correct
10 Incorrect 19 ms 23808 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 19 ms 23984 KB Output is correct
3 Correct 19 ms 23936 KB Output is correct
4 Correct 19 ms 23808 KB Output is correct
5 Correct 18 ms 23928 KB Output is correct
6 Correct 18 ms 23808 KB Output is correct
7 Correct 18 ms 23936 KB Output is correct
8 Correct 18 ms 23808 KB Output is correct
9 Correct 19 ms 23936 KB Output is correct
10 Incorrect 19 ms 23808 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 23808 KB Output is correct
2 Correct 19 ms 23984 KB Output is correct
3 Correct 19 ms 23936 KB Output is correct
4 Correct 19 ms 23808 KB Output is correct
5 Correct 18 ms 23928 KB Output is correct
6 Correct 18 ms 23808 KB Output is correct
7 Correct 18 ms 23936 KB Output is correct
8 Correct 18 ms 23808 KB Output is correct
9 Correct 19 ms 23936 KB Output is correct
10 Incorrect 19 ms 23808 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

# Verdict Execution time Memory Grader output
1 Execution timed out 10026 ms 53008 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 10026 ms 53008 KB Time limit exceeded
2 Halted 0 ms 0 KB -