Submission #1070142

#	Time	Username	Problem	Language	Result	Execution time	Memory
1070142		ArthuroWich	Distributing Candies (IOI21_candies)	C++17	0 / 100	1096 ms	30208 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 INT_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 INT_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);
    for (int i = 1; i <= q; 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++) {
        int ind = trav(q, c[i]);    
        if (ind == -1) {
            ans[i] = segs[1]-segmn[1];
            continue; 
        }
        int tmp2 = segs[1], tmp1 = querys(1, 0, q, 0, ind-1);
        //cout << tmp1 << " " << tmp2;
        if (tmp1 < tmp2) {
            int tmp3 = querymx(1, 0, q, ind-1, q);
            //cout << " " << tmp3 << endl;
            ans[i] = c[i] - (tmp3-tmp2);
        } else {
            int tmp3 = querymn(1, 0, q, ind-1, q);
            //cout << " " << tmp3 << endl;
            ans[i] = tmp2-tmp3;
        }
    }
    return ans;
}

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