oj.uz

Submission #441830

# Submission time Handle Problem Language Result Execution time Memory
441830 2021-07-06T10:15:44 Z baluteshih Distributing Candies (IOI21_candies) C++17
0 / 100
 379 ms 26220 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
#define X first
#define Y second
#define pb push_back
#define ALL(v) v.begin(), v.end()
#define SZ(a) ((int)a.size())

const ll INF = 1e18;
ll gc;
struct node {
    ll lazy; // add
    ll mx, mi;
    node(ll _mx = 0, ll _mi = 0):lazy(0), mx(_mx), mi(_mi){}
    node operator+(const node &a)const {
        return node(max(mx, a.mx), min(mi, a.mi));
    }
} seg[800005];

void lazytag(int rt, ll lazy) {
    if (lazy != 0) {
        seg[rt].lazy += lazy;
        if (lazy > 0) {
            seg[rt].mx = min(seg[rt].mx + lazy, gc);
            seg[rt].mi = min(seg[rt].mi + lazy, gc);
        }
        else {
            seg[rt].mx = max(seg[rt].mx + lazy, 0LL);
            seg[rt].mi = max(seg[rt].mi + lazy, 0LL);
        }
    }
}

void down(int rt) {
    lazytag(rt << 1, seg[rt].lazy);
    lazytag(rt << 1 | 1, seg[rt].lazy);
    seg[rt].lazy = 0;
}

void modify(int L, int R, int l, int r, int rt, ll v) {
    if (L <= l && R >= r)
        return lazytag(rt, v);
    down(rt);
    int mid = (l + r) >> 1;
    if (L <= mid)
        modify(L, R, l, mid, rt << 1, v);
    if (R > mid)
        modify(L, R, mid + 1, r, rt << 1 | 1, v);
    seg[rt] = seg[rt << 1] + seg[rt << 1 | 1];
}

void query(int l, int r, int rt, vector<int> &ans) {
    if (l == r)
        return ans[l] = seg[rt].mi, void();
    down(rt);
    int mid = (l + r) >> 1;
    query(l, mid, rt << 1, ans);
    query(mid + 1, r, rt << 1 | 1, ans);
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) {
    int n = c.size();
    vector<int> ans(n);
    gc = c[0];
    for (int i = 0; i < SZ(l); ++i)
        modify(l[i], r[i], 0, n - 1, 1, v[i]);
    query(0, n - 1, 1, ans);
    return ans;
}

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 29.0

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

Subtask #5
0 / 33.0

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