oj.uz

Submission #439294

# Submission time Handle Problem Language Result Execution time Memory
439294 2021-06-29T13:46:02 Z cheeheng Distributing Candies (IOI21_candies) C++17
27 / 100
 1024 ms 23396 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;

/*

min(max(min(x+2, 10)-5, 0)+3, 10)

= min(max(min(x-3, 5), 0)+3, 10)

= min(max(min(x, 8), 3), 10)

= max(min(x, 8), 3)


min( max(min(x+offset, max1), min1) + y, M )

= min( max(min(x+offset, max1)+y, min1+y), M )

= min( max(min(x+offset+y, max1+y), min1+y), M )

= max( min(min(x+offset+y, max1+y), M), min(min1+y, M) )

= max( min(x+offset+y, min(max1+y, M)), min(min1+y, M) )
*/

int M;
int n;

long long A[(1<<19)+5];
long long lazyMax[(1<<19)+5];
long long lazyMin[(1<<19)+5];
long long lazyOffset[(1<<19)+5];

void combineMin(int i, int y, long long M){
    long long max1 = min(lazyMax[i]+y, M);
    long long min1 = min(lazyMin[i]+y, M);
    //assert(min1 <= max1);
    //max1 = max(max1, min1);
    long long offset = lazyOffset[i] + y;

    lazyMax[i] = max1;
    lazyMin[i] = min1;
    lazyOffset[i] = offset;
}

/*
max( max(min(x+offset, max1), min1) + y, M )

= max( max(min(x+offset, max1)+y, min1+y), M )

= max( max(min(x+offset+y, max1+y), min1+y), M )

= max(min(x+offset+y, max1+y), max(min1+y, M))
*/

void combineMax(int i, int y, long long M){
    long long max1 = lazyMax[i]+y;
    long long min1 = max(lazyMin[i]+y, M);
    //assert(min1 <= max1);
    //max1 = max(max1, min1);
    long long offset = lazyOffset[i] + y;

    lazyMax[i] = max1;
    lazyMin[i] = min1;
    lazyOffset[i] = offset;
}

void init(int i = 1, int s = 0, int e = n-1){
    lazyMax[i] = M;
    lazyMin[i] = 0;
    lazyOffset[i] = 0;
    if(s == e){
        A[s] = 0;
        return;
    }else{
        int l = (i<<1);
        int r = (i<<1)|1;
        int m = (s+e)>>1;

        init(l, s, m);
        init(r, m+1, e);
    }
}

void propagate(int i, int s, int e){
    if(s == e){
        A[s] = max(min(A[s] + lazyOffset[i], lazyMax[i]), lazyMin[i]);

        lazyMax[i] = M;
        lazyMin[i] = 0;
        lazyOffset[i] = 0;
        return;
    }else{
        int l = (i<<1);
        int r = (i<<1)|1;

        combineMin(r, lazyOffset[i], lazyMax[i]);
        combineMax(r, 0, lazyMin[i]);

        combineMin(l, lazyOffset[i], lazyMax[i]);
        combineMax(l, 0, lazyMin[i]);

        lazyMax[i] = M;
        lazyMin[i] = 0;
        lazyOffset[i] = 0;
        return;
    }
}

void updateMin(int x, int y, int val, int i = 1, int s = 0, int e = n-1){
    propagate(i, s, e);
    if(x <= s && e <= y){
        combineMin(i, val, M);
        propagate(i, s, e);
        return;
    }else{
        int l = (i<<1);
        int r = (i<<1)|1;
        int m = (s+e)>>1;

        if(x > m){
            updateMin(x, y, val, r, m+1, e);
        }else if(y <= m){
            updateMin(x, y, val, l, s, m);
        }else{
            updateMin(x, y, val, r, m+1, e);
            updateMin(x, y, val, l, s, m);
        }
        propagate(l, s, m);
        propagate(r, m+1, e);
    }
    return;
}

void updateMax(int x, int y, int val, int i = 1, int s = 0, int e = n-1){
    propagate(i, s, e);
    if(x <= s && e <= y){
        combineMax(i, val, M);
        propagate(i, s, e);
        return;
    }else{
        int l = (i<<1);
        int r = (i<<1)|1;
        int m = (s+e)>>1;

        if(x > m){
            updateMin(x, y, val, r, m+1, e);
        }else if(y <= m){
            updateMin(x, y, val, l, s, m);
        }else{
            updateMin(x, y, val, r, m+1, e);
            updateMin(x, y, val, l, s, m);
        }
        propagate(l, s, m);
        propagate(r, m+1, e);
    }
    return;
}

long long query(int p, int i = 1, int s = 0, int e = n-1){
    propagate(i, s, e);
    if(s == e){
        return A[s];
    }else{
        int l = (i<<1);
        int r = (i<<1)|1;
        int m = (s+e)>>1;
        if(p > m){
            return query(p, r, m+1, e);
        }else{
            return query(p, l, s, m);
        }
    }
}

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    n = (int)c.size();
    int q = (int)l.size();
    M = c[0];
    vector<long long> ans(n);
    vector<int> ans2(n);

    for(int i = 0; i < n; i ++){
        ans[i] = 0;
    }

    init();

    for(int i = 0; i < q; i ++){
        if(v[i] > 0){
            updateMin(l[i], r[i], v[i]);
        }else{
            updateMax(l[i], r[i], v[i]);
        }
    }

    for(int i = 0; i < n; i ++){
        ans2[i] = query(i);
    }

    return ans2;
}

Subtask #1
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 1024 ms 22808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 371 ms 5176 KB Output is correct
3 Correct 155 ms 18104 KB Output is correct
4 Correct 989 ms 22804 KB Output is correct
5 Correct 991 ms 23396 KB Output is correct
6 Correct 999 ms 23368 KB Output is correct
7 Correct 1004 ms 23316 KB Output is correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 1 ms 204 KB Output isn't correct
3 Halted 0 ms 0 KB -