Submission #558917

#	Time	Username	Problem	Language	Result	Execution time	Memory
558917		nghiass001	Distributing Candies (IOI21_candies)	C++17	100 / 100	425 ms	34192 KiB

candies

#include "candies.h"
#include <bits/stdc++.h>
#define FOR(i,l,r) for(int i=(l); i<=(r); ++i)
#define REP(i,l,r) for(int i=(l); i<(r); ++i)
#define FORD(i,r,l) for(int i=(r); i>=(l); --i)
#define REPD(i,r,l) for(int i=(r)-1; i>=(l); --i)
using namespace std;
const int N = 2e5 + 5;
int n, q;
long long lazy[N * 4], vmin[N * 4], vmax[N * 4];
long long minF, maxF;
vector<int> Q[N];

void down(int range, int pos) {
    if (lazy[pos]) {
        vmin[pos] += lazy[pos];
        vmax[pos] += lazy[pos];
        if (range) {
            lazy[pos * 2] += lazy[pos];
            lazy[pos * 2 + 1] += lazy[pos];
        }
        lazy[pos] = 0;
    }
}

void update(int x, int y, int val, int l = 0, int r = q, int pos = 1) {
    if (x > r || y < l || x > y) return;
    if (x <= l && r <= y) {
        lazy[pos] += val;
        return;
    }
    down(r - l, pos);
    int mid = (l + r) / 2;
    update(x, y, val, l, mid, pos * 2);
    update(x, y, val, mid + 1, r, pos * 2 + 1);
    vmin[pos] = min(vmin[pos * 2] + lazy[pos * 2], vmin[pos * 2 + 1] + lazy[pos * 2 + 1]);
    vmax[pos] = max(vmax[pos * 2] + lazy[pos * 2], vmax[pos * 2 + 1] + lazy[pos * 2 + 1]);
}

int query(int diff, int l = 0, int r = q, int pos = 1) {
    down(r - l, pos);
    if (max(maxF, vmax[pos]) - min(minF, vmin[pos]) < diff) {
        maxF = max(maxF, vmax[pos]);
        minF = min(minF, vmin[pos]);
        return l - 1;
    }
    if (l == r) {
        maxF = max(maxF, vmax[pos]);
        minF = min(minF, vmin[pos]);
        if (maxF == vmax[pos]) maxF = minF + diff;
        else minF = maxF - diff;
        return l;
    }

    int mid = (l + r) / 2;
    int tmp = query(diff, mid + 1, r, pos * 2 + 1);
    if (tmp > mid) return tmp;
    return query(diff, l, mid, pos * 2);
}

vector<int> distribute_candies(vector<int> c, vector<int> l,
                                    vector<int> r, vector<int> v) {
    n = c.size();
    q = v.size();
    vector<int> ans(n, 0);

    REP(i, 0, q) {
        Q[l[i]].push_back(i);
        Q[r[i] + 1].push_back(i + q);
    }

    REP(i, 0, n) {
        for(int id : Q[i]) {
            if (id < q) update(0, id, v[id]);
            else update(0, id - q, -v[id - q]);
        }
        minF = maxF = 0;
        int tmp = query(c[i]);
        ans[i] = maxF;
    }

    return ans;
}

Compilation message (stderr)

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:78:13: warning: unused variable 'tmp' [-Wunused-variable]
   78 |         int tmp = query(c[i]);
      |             ^~~

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