Submission #1198037

#	Time	Username	Problem	Language	Result	Execution time	Memory
1198037		yellowtoad	Distributing Candies (IOI21_candies)	C++20	100 / 100	725 ms	30092 KiB

candies

#include "candies.h"
#include <iostream>
#include <vector>
#include <algorithm>
#define f first
#define s second
using namespace std;

int n, q;
vector<int> op[200010];

struct {
    struct {
        long long maxx, minn, lz;
    } node[800010];

    void split(int id) {
        node[id*2].maxx += node[id].lz;
        node[id*2].minn += node[id].lz;
        node[id*2+1].maxx += node[id].lz;
        node[id*2+1].minn += node[id].lz;
        node[id*2].lz += node[id].lz;
        node[id*2+1].lz += node[id].lz;
        node[id].lz = 0;
    }

    void update(int id, int x, int y, int pos, long long val) {
        if (pos <= x) {
            node[id].maxx += val;
            node[id].minn += val;
            node[id].lz += val;
            return;
        }
        if (y < pos) return;
        int mid = (x+y)/2;
        split(id);
        update(id*2,x,mid,pos,val);
        update(id*2+1,mid+1,y,pos,val);
        node[id].maxx = max(node[id*2].maxx,node[id*2+1].maxx);
        node[id].minn = min(node[id*2].minn,node[id*2+1].minn);
    }

    long long findmax(int id, int x, int y, int pos) {
        if (pos <= x) return node[id].maxx;
        if (y < pos) return -1e18;
        int mid = (x+y)/2;
        split(id);
        return max(findmax(id*2,x,mid,pos),findmax(id*2+1,mid+1,y,pos));
    }

    long long findmin(int id, int x, int y, int pos) {
        if (pos <= x) return node[id].minn;
        if (y < pos) return 1e18;
        int mid = (x+y)/2;
        split(id);
        return min(findmin(id*2,x,mid,pos),findmin(id*2+1,mid+1,y,pos));
    }

} seg;

std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    n = c.size();
    reverse(v.begin(),v.end());
    reverse(l.begin(),l.end());
    reverse(r.begin(),r.end());
    l.push_back(0); l.push_back(0);
    r.push_back(n-1); r.push_back(n-1);
    v.push_back(-2e9); v.push_back(2e9);
    reverse(v.begin(),v.end());
    reverse(l.begin(),l.end());
    reverse(r.begin(),r.end());
    q = v.size();
    vector<int> ans(n);
    for (int i = 0; i < q; i++) {
        op[l[i]].push_back(i);
        op[r[i]+1].push_back(i);
    }
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < op[i].size(); j++) {
            if (i == l[op[i][j]]) seg.update(1,0,q-1,op[i][j],v[op[i][j]]);
            else seg.update(1,0,q-1,op[i][j],-v[op[i][j]]);
        }
        int l = 0, r = q-1;
        while (l <= r) {
            int mid = (l+r)/2;
            if (seg.findmax(1,0,q-1,mid)-seg.findmin(1,0,q-1,mid) >= c[i]) l = mid+1;
            else r = mid-1;
        }
        if (v[l] < 0) ans[i] = seg.findmax(1,0,q-1,q-1)-seg.findmin(1,0,q-1,l);
        else ans[i] = c[i]-seg.findmax(1,0,q-1,l)+seg.findmin(1,0,q-1,q-1);
    }
    return ans;
}

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