Submission #1070255

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070255		ArthuroWich	Distributing Candies (IOI21_candies)	C++17	100 / 100	1582 ms	54272 KiB

candies

#include "candies.h"
#include<bits/stdc++.h>
using namespace std;
#define int long long int
int segs[4*200005], segmx[4*200005], segmn[4*200005], lazy[4*200005];
void lazypropagate(int n, int l, int r) {
    if (lazy[n]) {
        segmn[n] += lazy[n];
        segmx[n] += lazy[n];
        if (l != r) {
            lazy[2*n] += lazy[n];
            lazy[2*n+1] += lazy[n];
        }
        lazy[n] = 0;
    }
}
void updates(int n, int l, int r, int i, int v) {
    if (l == r) {
        segs[n] += v;
    } else {
        int m = (l+r)/2;
        if (l <= i && i <= m) {
            updates(2*n, l, m, i, v);
        } else {
            updates(2*n+1, m+1, r, i, v);
        }
        segs[n] = segs[2*n] + segs[2*n+1];
    }
}
void updatem(int n, int l, int r, int a, int b, int v) {
    lazypropagate(n, l, r);
    if (b < l || r < a) {
        return;
    } else if (a <= l && r <= b) {
        lazy[n] += v;
        lazypropagate(n, l, r);
    } else {
        int m = (l+r)/2;
        updatem(2*n, l, m, a, b, v);
        updatem(2*n+1, m+1, r, a, b, v);
        segmn[n] = min(segmn[2*n], segmn[2*n+1]);
        segmx[n] = max(segmx[2*n], segmx[2*n+1]);
    }
}
int querys(int n, int l, int r, int a, int b) {
    if (b < l || r < a) {
        return 0;
    } else if (a <= l && r <= b) {
        return segs[n];
    } else {
        int m = (l+r)/2;
        return querys(2*n, l, m, a, b) + querys(2*n+1, m+1, r, a, b);
    }
}
int querymn(int n, int l, int r, int a, int b) {
    if (b < l || r < a) {
        return INT64_MAX;
    }
    lazypropagate(n, l, r); 
    if (a <= l && r <= b) {
        return segmn[n];
    } else {
        int m = (l+r)/2;
        return min(querymn(2*n, l, m, a, b), querymn(2*n+1, m+1, r, a, b));
    }
}
int querymx(int n, int l, int r, int a, int b) {
    if (b < l || r < a) {
        return INT64_MIN;
    }
    lazypropagate(n, l, r); 
    if (a <= l && r <= b) {
        return segmx[n];
    } else {
        int m = (l+r)/2;
        return max(querymx(2*n, l, m, a, b), querymx(2*n+1, m+1, r, a, b));
    }
}
int trav(int q, int c) {
    int l = 0, r = q;
    while(l < r) {
        int m = (l+r+1)/2;
        if (querymx(1, 0, q, m, q)-querymn(1, 0, q, m, q) > c) {
            l = m;
        } else {
            r = m-1;
        }
    }
    if (querymx(1, 0, q, l, q)-querymn(1, 0, q, l, q) > c) {
        return l;
    } else {
        return -1;
    }
}
vector<int32_t> distribute_candies(vector<int32_t> c, vector<int32_t> l, vector<int32_t> r, vector<int32_t> v) {
    int n = c.size(), q = l.size();
    vector<int32_t> ans(n);
    vector<vector<int>> le(n), ri(n);
    for (int i = 1; i <= q; i++) {
        le[l[i-1]].push_back(i);
        if (r[i-1]+1 < n) {
            ri[r[i-1]+1].push_back(i);
        }
        //updatem(1, 0, q, i, q, v[i-1]);
        //updates(1, 0, q, i, v[i-1]);
    }
    for (int i = 0; i < n; i++) {
        for (int j : le[i]) {
            updatem(1, 0, q, j, q, v[j-1]);
            updates(1, 0, q, j, v[j-1]);
        }
        for (int j : ri[i]) {
            updatem(1, 0, q, j, q, -v[j-1]);
            updates(1, 0, q, j, -v[j-1]);
        }
        int ind = trav(q, c[i]);    
        if (ind == -1) {
            ans[i] = segs[1]-querymn(1, 0, q, 0, q);
            continue; 
        }
        if (segs[1] > querys(1, 0, q, 0, ind)) {
            ans[i] = c[i]-(querymx(1, 0, q, ind, q)-segs[1]);
        } else {
            ans[i] = segs[1]-querymn(1, 0, q, ind, q);
        }
    }
    return ans;
}

• Subtask 1: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33