oj.uz

Submission #443384

# Submission time Handle Problem Language Result Execution time Memory
443384 2021-07-10T12:29:13 Z mjhmjh1104 Distributing Candies (IOI21_candies) C++17
35 / 100
 1148 ms 16016 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; 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 < n; i++) {
        if (part_curr[i] + block_gain[i / block].l < 0) part_curr[i] = block_gain[i / block].c - block_gain[i / block].l;
        else if (part_curr[i] + block_gain[i / block].r > c[i]) part_curr[i] = block_gain[i / block].c - block_gain[i / block].r + c[i];
        else part_curr[i] += block_gain[i / block].c;
        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 10 ms 1484 KB Output isn't correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 925 ms 9312 KB Output is correct
2 Correct 972 ms 9316 KB Output is correct
3 Correct 1148 ms 9312 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 560 ms 6236 KB Output is correct
3 Correct 77 ms 5824 KB Output is correct
4 Correct 832 ms 9316 KB Output is correct
5 Correct 839 ms 15624 KB Output is correct
6 Correct 772 ms 16016 KB Output is correct
7 Correct 678 ms 15272 KB Output is correct

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 993 ms 6212 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 10 ms 1484 KB Output isn't correct