제출 #443382

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
443382		mjhmjh1104	Distributing Candies (IOI21_candies)	C++17	0 / 100	1004 ms	9260 KiB

candies

#include "candies.h"
#include <cstdio>
#include <vector>
using namespace std;

struct Gain {
    long long l = 0;
    long long r = 0;
    long long c = 0;
};

int block = 550;
int part_curr[310006];
Gain block_gain[556];
vector<int> c;

void update_block_gain(int t) {
    for (int i = block * t; i < block * t + block; i++) {
        if ((int)c.size() <= i) break;
        if (part_curr[i] + block_gain[t].l < 0) part_curr[i] = block_gain[t].c - block_gain[t].l;
        else if (part_curr[i] + block_gain[t].r > c[i]) part_curr[i] = block_gain[t].c - block_gain[t].r + c[i];
        else part_curr[i] += block_gain[t].c;
    }
    block_gain[t].l = block_gain[t].r = block_gain[t].c = 0;
}

vector<int> distribute_candies(vector<int> C, vector<int> l, vector<int> r, vector<int> v) {
    c = C;
    for (int i = 0; i < 300006; i++) part_curr[i] = 0;
    for (int i = 0; i < 556; i++) block_gain[i].l = block_gain[i].r = block_gain[i].c = 0;
    int n = (int)c.size(), q = (int)v.size();
    vector<int> s(n);
    for (int t = 0; t < q; t++) {
        int l_block = l[t] / block, r_block = r[t] / block;
        if (l_block == r_block) {
            update_block_gain(l_block);
            for (int i = l[t]; i <= r[t]; i++) {
                part_curr[i] += v[t];
                if (part_curr[i] < 0) part_curr[i] = 0;
                if (part_curr[i] > c[i]) part_curr[i] = c[i];
            }
        } else {
            update_block_gain(l_block);
            update_block_gain(r_block);
            for (int i = l[t]; i < block * l_block + block; i++) {
                part_curr[i] += v[t];
                if (part_curr[i] < 0) part_curr[i] = 0;
                if (part_curr[i] > c[i]) part_curr[i] = c[i];
            }
            for (int i = block * r_block; i <= r[t]; i++) {
                part_curr[i] += v[t];
                if (part_curr[i] < 0) part_curr[i] = 0;
                if (part_curr[i] > c[i]) part_curr[i] = c[i];
            }
            for (int i = l_block + 1; i < r_block - 1; i++) {
                block_gain[i].c += v[t];
                block_gain[i].l = min(block_gain[i].l, block_gain[i].c);
                block_gain[i].r = min(block_gain[i].r, block_gain[i].l + c[0]);
                block_gain[i].r = max(block_gain[i].r, block_gain[i].c);
                block_gain[i].l = max(block_gain[i].l, block_gain[i].r - c[0]);
            }
        }
    }
    for (int i = 0; i < 556; i++) update_block_gain(i);
    for (int i = 0; i < n; i++) s[i] = part_curr[i];
    return s;
}

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