Submission #438772

#	Time	Username	Problem	Language	Result	Execution time	Memory
438772		cheeheng	Distributing Candies (IOI21_candies)	C++17	0 / 100	1002 ms	22804 KiB

candies

#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, min1), max1) + y, M )

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

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

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

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

= max( min(x+offset+y, min(min1+y, M)), min(max1+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);
    long long offset = lazyOffset[i] + y;

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

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

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

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

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

void combineMax(int i, int y, long long M){
    long long max1 = max(lazyMax[i]+y, M);
    long long min1 = lazyMin[i]+y;
    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(s <= x && 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
• Subtask 2: 0 / 8
• Subtask 3: 0 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33