oj.uz

Submission #443382

# Submission time Handle Problem Language Result Execution time Memory
443382 2021-07-10T12:18:22 Z mjhmjh1104 Distributing Candies (IOI21_candies) C++17
0 / 100
 1004 ms 9260 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1356 KB Output is correct
2 Correct 1 ms 1356 KB Output is correct
3 Correct 2 ms 1484 KB Output is correct
4 Correct 2 ms 1484 KB Output is correct
5 Incorrect 9 ms 1484 KB Output isn't correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 833 ms 9260 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1356 KB Output is correct
2 Incorrect 539 ms 6208 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1356 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Incorrect 1004 ms 6200 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1356 KB Output is correct
2 Correct 1 ms 1356 KB Output is correct
3 Correct 2 ms 1484 KB Output is correct
4 Correct 2 ms 1484 KB Output is correct
5 Incorrect 9 ms 1484 KB Output isn't correct