oj.uz

Submission #160015

# Submission time Handle Problem Language Result Execution time Memory
160015 2019-10-25T16:47:53 Z georgerapeanu Two Dishes (JOI19_dishes) C++11
10 / 100
 10000 ms 41120 KB 
#include <cstdio>
#include <algorithm>
#include <vector>

using namespace std;

const int NMAX = 1e6;
const bool HOME = 0;
const long long inf = 1e17;

int n,m;
int a[NMAX + 5];
int b[NMAX + 5];
int p[NMAX + 5];
int q[NMAX + 5];
long long s[NMAX + 5];
long long t[NMAX + 5];

int pref_lin[NMAX + 5];
int pref_col[NMAX + 5];

long long dp[100][100];

vector<int> event[NMAX + 5];

struct node_t{
    int base_offset;
    long long sum;
    long long val;
    int lazy;

    node_t operator + (const node_t &other)const{
        node_t ans;
        ans.base_offset = 0;
        ans.sum = (this->sum) + other.sum;
        ans.val = 0;
        ans.lazy = 0;
        return ans;
    }
}aint[4 * NMAX + 5];

void propag(int nod,int st,int dr){
    if(st == dr || aint[nod].lazy == 0){
        return ;
    }
    
    aint[2 * nod].lazy |= aint[nod].lazy;
    aint[2 * nod + 1].lazy |= aint[nod].lazy;
    
    aint[2 * nod].val = aint[2 * nod].sum = 0;
    aint[2 * nod + 1].val = aint[2 * nod + 1].sum = 0;

    aint[nod].lazy = 0;
}

void build(int nod,int st,int dr){
    aint[nod].base_offset = 0;
    aint[nod].sum = 0;
    aint[nod].val = 0;
    aint[nod].lazy = 0;

    if(st == dr){
        return ;
    }

    int mid = (st + dr) / 2;

    build(nod * 2,st,mid);
    build(nod * 2 + 1,mid + 1,dr);
}

void update_val(int nod,int st,int dr,int pos,int delta){///+= delta
    propag(nod,st,dr);

    if(dr < pos || st > pos){
        return ;
    }

    if(st == dr){
        aint[nod].val += delta;
        if(st != 0)aint[nod].val = max(0LL,aint[nod].val);
        aint[nod].sum = aint[nod].val;
        return ;
    }

    int mid = (st + dr) / 2;

    update_val(nod * 2,st,mid,pos,delta);
    update_val(nod * 2 + 1,mid + 1,dr,pos,delta);
        
    aint[nod] = aint[nod * 2] + aint[nod * 2 + 1];
}

void update_offset(int nod,int st,int dr,int pos,int delta,bool initial = false){/// += delta_offset
    propag(nod,st,dr);
    if(dr < pos || st > pos){
        return ;
    }

    if(st == dr){
        aint[nod].base_offset += delta;
        if(initial == false){
            aint[nod].val -= delta;
            aint[nod].val = max(aint[nod].val,0LL);
        }
        aint[nod].sum = aint[nod].val;
        return ;
    }

    int mid = (st + dr) / 2;

    update_offset(nod * 2,st,mid,pos,delta,initial);
    update_offset(nod * 2 + 1,mid + 1,dr,pos,delta,initial);
    
    aint[nod] = aint[nod * 2] + aint[nod * 2 + 1];
}

void update_0(int nod,int st,int dr,int l,int r){
    propag(nod,st,dr);
    if(r < st || l > dr){
        return ;
    }
    if(l <= st && dr <= r){
        aint[nod].lazy = 1;
        aint[nod].sum = 0;
        aint[nod].val = 0;
        return ;
    }

    int mid = (st + dr) / 2;

    update_0(nod * 2,st,mid,l,r);
    update_0(nod * 2 + 1,mid + 1,dr,l,r);

    aint[nod] = aint[nod * 2] + aint[nod * 2 + 1];
}
long long query_sum(int nod,int st,int dr,int l,int r){
    propag(nod,st,dr);
    if(r < st || l > dr){
        return 0;
    }
    
    if(l <= st && dr <= r){
        return aint[nod].sum;
    }
    
    int mid = (st + dr) / 2;

    return query_sum(nod * 2,st,mid,l,r) + query_sum(nod * 2 + 1,mid + 1,dr,l,r);
}

long long get_val(int nod,int st,int dr,int pos){
    propag(nod,st,dr);
    if(dr < pos || st > pos){
        return -1;
    }
    
    if(st == dr){
        return aint[nod].val;
    }

    int mid = (st + dr) / 2;

    return max(get_val(nod * 2,st,mid,pos),get_val(nod * 2 + 1,mid + 1,dr,pos));
}

int get_pos_sum(int pos,int elem){///TODO can be improved
   int l = pos - 1,r = n + 1;
    while(r - l > 1){
        int mid = (l + r) / 2;
        if(query_sum(1,0,n,pos,mid) + elem >= 0){
            r = mid;
        }
        else{
            l = mid;
        }
    }

    return r;
}

long long get_time(int i,int j){
    static int last_lin = 0;
    static int last_col = 0;
    static long long last_sum = 0;

    while(last_lin > i){
        last_sum -= a[last_lin];
        last_lin--;
    }
    
    while(last_lin < i){
        last_lin++;
        last_sum += a[last_lin];
    }

    while(last_col > j){
        last_sum -= b[last_col];
        last_col--;
    }

    while(last_col < j){
        last_col++;
        last_sum += b[last_col];
    }

    return last_sum;
}

void afis(int nod,int st,int dr,long long &sum){
    propag(nod,st,dr);
    if(st == dr){
    //    sum += aint[nod].val + aint[nod].base_offset;
        printf("(%lld,%lld) ",aint[nod].val,aint[nod].base_offset);
        return ;
    }
    
    int mid = (st + dr) / 2;
    afis(nod * 2,st,mid,sum);
    afis(nod * 2 + 1,mid + 1,dr,sum);
}

long long get_ans(int nod,int st,int dr){
    propag(nod,st,dr);
    if(st == dr){
        return (aint[nod].val + aint[nod].base_offset);
    }

    int mid = (st + dr) / 2;

    return get_ans(nod * 2,st,mid) + get_ans(nod * 2 + 1,mid + 1,dr);
}

int main(){

    scanf("%d %d",&n,&m);

    for(int i = 1;i <= n;i++){
        scanf("%d %lld %d",&a[i],&s[i],&p[i]);
    }
    
    for(int i = 1;i <= m;i++){
        scanf("%d %lld %d",&b[i],&t[i],&q[i]);
    }

    for(int j = 0;j <= m;j++){
        int l = -1,r = n + 1;
        while(r - l > 1){
            int mid = (l + r) / 2;
            if(get_time(mid,j) <= t[j]){
                l = mid;
            }
            else{
                r = mid;
            }
        }

        pref_col[j] =  l;
    }


    for(int i = 0;i <= n;i++){
        int l = -1,r = m + 1;

        while(r - l > 1){
            int mid = (l + r) / 2;
            if(get_time(i,mid) <= s[i]){
                l = mid;
            }
            else{
                r = mid;
            }
        }

        pref_lin[i] = l;
    }

    if(HOME){
    printf("STARTDP\n");
    for(int j = 0;j <= m;j++){
        for(int i = 0;i <= n;i++){
            if(i == 0 && j == 0){
                dp[i][j] = 0;
            }
            else{
                if(i != 0){
                    dp[i][j] = dp[i - 1][j] + p[i] * (pref_lin[i] >= j);
                    if(j > 0){
                        dp[i][j] = max(dp[i][j],dp[i][j - 1] + q[j] * (pref_col[j] >= i));
                    }
                }
                else{
                    dp[i][j] = dp[i][j - 1] + q[j] * (pref_col[j] >= i);
                }
            }
            printf("%lld ",dp[i][j]);
        }
        printf("\n");
    }
    printf("ENDDP\n");
    }

    build(1,0,n);

    for(int i = 1;i <= n;i++){
        if(pref_lin[i] > -1){
            update_offset(1,0,n,i,p[i],true);
            event[pref_lin[i] + 1].push_back(i);
        }
    }
    if(HOME){long long tmp = 0;afis(1,0,n,tmp);printf("\n");}
    for(int j = 1;j <= m;j++){
        for(auto it:event[j]){
            update_offset(1,0,n,it,-p[it]);
           if(HOME) printf("rem offset %d %d\n",it,-p[it]);
        }
        if(pref_col[j] > -1){
            update_val(1,0,n,0,q[j]);
            if(HOME)printf("col trans %d %d\n",pref_col[j] + 1,-q[j]);
            int k = get_pos_sum(pref_col[j] + 1,-q[j]);
            if(HOME)printf("pos found %d\n",k);
            if(k <= n){
                update_val(1,0,n,k,(query_sum(1,0,n,pref_col[j] + 1,k) - q[j]) - get_val(1,0,n,k));
            }
            if(pref_col[j] + 1 <= k - 1){
                update_0(1,0,n,pref_col[j] + 1,k - 1);
            }
        }
        if(HOME){long long tmp = 0;afis(1,0,n,tmp);printf("\n");}
    }

    printf("%lld\n",get_ans(1,0,n));

    return 0;
}

Compilation message

dishes.cpp: In function 'void afis(int, int, int, long long int&)':
dishes.cpp:214:66: warning: format '%lld' expects argument of type 'long long int', but argument 3 has type 'int' [-Wformat=]
         printf("(%lld,%lld) ",aint[nod].val,aint[nod].base_offset);
                                             ~~~~~~~~~~~~~~~~~~~~~^
dishes.cpp: In function 'int main()':
dishes.cpp:236: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:239:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %lld %d",&a[i],&s[i],&p[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
dishes.cpp:243:14: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
         scanf("%d %lld %d",&b[i],&t[i],&q[i]);
         ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 5.0

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

Subtask #2
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 23800 KB Output is correct
2 Correct 24 ms 23948 KB Output is correct
3 Correct 24 ms 23928 KB Output is correct
4 Correct 24 ms 23928 KB Output is correct
5 Correct 24 ms 23928 KB Output is correct
6 Correct 23 ms 23928 KB Output is correct
7 Correct 24 ms 23800 KB Output is correct
8 Correct 23 ms 23928 KB Output is correct
9 Correct 23 ms 23928 KB Output is correct
10 Correct 23 ms 23928 KB Output is correct
11 Correct 23 ms 23800 KB Output is correct
12 Correct 54 ms 23928 KB Output is correct
13 Correct 24 ms 23928 KB Output is correct
14 Correct 24 ms 23928 KB Output is correct
15 Correct 23 ms 23928 KB Output is correct
16 Correct 24 ms 23804 KB Output is correct

Subtask #3
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 23800 KB Output is correct
2 Correct 24 ms 23948 KB Output is correct
3 Correct 24 ms 23928 KB Output is correct
4 Correct 24 ms 23928 KB Output is correct
5 Correct 24 ms 23928 KB Output is correct
6 Correct 23 ms 23928 KB Output is correct
7 Correct 24 ms 23800 KB Output is correct
8 Correct 23 ms 23928 KB Output is correct
9 Correct 23 ms 23928 KB Output is correct
10 Correct 23 ms 23928 KB Output is correct
11 Correct 23 ms 23800 KB Output is correct
12 Correct 54 ms 23928 KB Output is correct
13 Correct 24 ms 23928 KB Output is correct
14 Correct 24 ms 23928 KB Output is correct
15 Correct 23 ms 23928 KB Output is correct
16 Correct 24 ms 23804 KB Output is correct
17 Correct 48 ms 24312 KB Output is correct
18 Correct 37 ms 24124 KB Output is correct
19 Correct 38 ms 24280 KB Output is correct
20 Correct 34 ms 24184 KB Output is correct
21 Correct 38 ms 24184 KB Output is correct
22 Correct 38 ms 24056 KB Output is correct
23 Correct 38 ms 24312 KB Output is correct

Subtask #4
0 / 39.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 23800 KB Output is correct
2 Correct 24 ms 23948 KB Output is correct
3 Correct 24 ms 23928 KB Output is correct
4 Correct 24 ms 23928 KB Output is correct
5 Correct 24 ms 23928 KB Output is correct
6 Correct 23 ms 23928 KB Output is correct
7 Correct 24 ms 23800 KB Output is correct
8 Correct 23 ms 23928 KB Output is correct
9 Correct 23 ms 23928 KB Output is correct
10 Correct 23 ms 23928 KB Output is correct
11 Correct 23 ms 23800 KB Output is correct
12 Correct 54 ms 23928 KB Output is correct
13 Correct 24 ms 23928 KB Output is correct
14 Correct 24 ms 23928 KB Output is correct
15 Correct 23 ms 23928 KB Output is correct
16 Correct 24 ms 23804 KB Output is correct
17 Correct 48 ms 24312 KB Output is correct
18 Correct 37 ms 24124 KB Output is correct
19 Correct 38 ms 24280 KB Output is correct
20 Correct 34 ms 24184 KB Output is correct
21 Correct 38 ms 24184 KB Output is correct
22 Correct 38 ms 24056 KB Output is correct
23 Correct 38 ms 24312 KB Output is correct
24 Execution timed out 10097 ms 41120 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #5
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 23800 KB Output is correct
2 Correct 24 ms 23948 KB Output is correct
3 Correct 24 ms 23928 KB Output is correct
4 Correct 24 ms 23928 KB Output is correct
5 Correct 24 ms 23928 KB Output is correct
6 Correct 23 ms 23928 KB Output is correct
7 Correct 24 ms 23800 KB Output is correct
8 Correct 23 ms 23928 KB Output is correct
9 Correct 23 ms 23928 KB Output is correct
10 Correct 23 ms 23928 KB Output is correct
11 Correct 23 ms 23800 KB Output is correct
12 Correct 54 ms 23928 KB Output is correct
13 Correct 24 ms 23928 KB Output is correct
14 Correct 24 ms 23928 KB Output is correct
15 Correct 23 ms 23928 KB Output is correct
16 Correct 24 ms 23804 KB Output is correct
17 Correct 48 ms 24312 KB Output is correct
18 Correct 37 ms 24124 KB Output is correct
19 Correct 38 ms 24280 KB Output is correct
20 Correct 34 ms 24184 KB Output is correct
21 Correct 38 ms 24184 KB Output is correct
22 Correct 38 ms 24056 KB Output is correct
23 Correct 38 ms 24312 KB Output is correct
24 Execution timed out 10097 ms 41120 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 46 ms 23800 KB Output is correct
2 Correct 24 ms 23948 KB Output is correct
3 Correct 24 ms 23928 KB Output is correct
4 Correct 24 ms 23928 KB Output is correct
5 Correct 24 ms 23928 KB Output is correct
6 Correct 23 ms 23928 KB Output is correct
7 Correct 24 ms 23800 KB Output is correct
8 Correct 23 ms 23928 KB Output is correct
9 Correct 23 ms 23928 KB Output is correct
10 Correct 23 ms 23928 KB Output is correct
11 Correct 23 ms 23800 KB Output is correct
12 Correct 54 ms 23928 KB Output is correct
13 Correct 24 ms 23928 KB Output is correct
14 Correct 24 ms 23928 KB Output is correct
15 Correct 23 ms 23928 KB Output is correct
16 Correct 24 ms 23804 KB Output is correct
17 Correct 48 ms 24312 KB Output is correct
18 Correct 37 ms 24124 KB Output is correct
19 Correct 38 ms 24280 KB Output is correct
20 Correct 34 ms 24184 KB Output is correct
21 Correct 38 ms 24184 KB Output is correct
22 Correct 38 ms 24056 KB Output is correct
23 Correct 38 ms 24312 KB Output is correct
24 Execution timed out 10097 ms 41120 KB Time limit exceeded
25 Halted 0 ms 0 KB -

Subtask #7
0 / 17.0

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