oj.uz

Submission #531243

# Submission time Handle Problem Language Result Execution time Memory
531243 2022-02-28T08:21:22 Z alextodoran Distributing Candies (IOI21_candies) C++17
0 / 100
 354 ms 41140 KB 
/**
 ____ ____ ____ ____ ____
||a |||t |||o |||d |||o ||
||__|||__|||__|||__|||__||
|/__\|/__\|/__\|/__\|/__\|

**/

#include <bits/stdc++.h>
#include "candies.h"

using namespace std;

typedef long long ll;

const int N_MAX = 200000;

struct SGTNode {
    ll delta;
    ll minVal;
    ll maxVal;
    void setVal (const int &v) {
        delta = v;
        minVal = min((ll) 0, -delta);
        maxVal = max((ll) 0, -delta);
    }
};
SGTNode operator + (const SGTNode &u, const SGTNode &v) {
    SGTNode w;
    w.delta = u.delta + v.delta;
    w.minVal = min(v.minVal, -v.delta + u.minVal);
    w.maxVal = max(v.maxVal, -v.delta + u.maxVal);
    return w;
}

int N;
SGTNode SGT[N_MAX * 4 + 2];

void build (int node, int l, int r) {
    if (l == r) {
        SGT[node].setVal(0);
        return;
    }
    int mid = (l + r) / 2;
    int lSon = node * 2, rSon = node * 2 + 1;
    build(lSon, l, mid);
    build(rSon, mid + 1, r);
    SGT[node] = SGT[lSon] + SGT[rSon];
}
void build (int n) {
    N = n;
    build(1, 1, N);
}
void update (int node, int l, int r, int pos, int val) {
    if (l == r) {
        SGT[node].setVal(val);
        return;
    }
    int mid = (l + r) / 2;
    int lSon = node * 2, rSon = node * 2 + 1;
    if (pos <= mid) {
        update(lSon, l, mid, pos, val);
    } else {
        update(rSon, mid + 1, r, pos, val);
    }
    SGT[node] = SGT[lSon] + SGT[rSon];
}
void update (int pos, int val) {
    update(1, 1, N, pos + 1, val);
}
ll query (int node, int l, int r, ll currMin, ll currMax, int diff) {
    if (l == r) {
        int excess = (max(currMax, SGT[node].maxVal) - min(currMin, SGT[node].minVal)) - diff;
        if (SGT[node].delta > 0) {
            return +excess;
        } else {
            return -excess - diff;
        }
    }
    int mid = (l + r) / 2;
    int lSon = node * 2, rSon = node * 2 + 1;
    ll minr = min(currMin, SGT[rSon].minVal);
    ll maxr = max(currMax, SGT[rSon].maxVal);
    if (maxr - minr >= diff) {
        return SGT[lSon].delta + query(rSon, mid + 1, r, currMin, currMax, diff);
    } else {
        return query(lSon, l, mid, minr + SGT[rSon].delta, maxr + SGT[rSon].delta, diff);
    }
}
ll query (int diff) {
    return query(1, 1, N, 0, 0, diff);
}

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

    vector <int> evAdd[n], evDel[n];
    for (int i = 0; i < q; i++) {
        evAdd[l[i]].push_back(i);
        evDel[r[i]].push_back(i);
    }

    build(q);
    vector <int> answer (n);
    for (int i = 0; i < n; i++) {
        for (int j : evAdd[i]) {
            update(j, v[j]);
        }
        answer[i] = SGT[1].delta - query(c[i]);
        for (int j : evDel[i]) {
            update(j, 0);
        }
    }
    return answer;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 29.0

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

Subtask #5
0 / 33.0

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