oj.uz

Submission #596109

# Submission time Handle Problem Language Result Execution time Memory
596109 2022-07-14T11:41:48 Z keta_tsimakuridze Distributing Candies (IOI21_candies) C++17
3 / 100
 5000 ms 17276 KB 
#include "candies.h"
#include<bits/stdc++.h>
#define pii pair<int,int>
#define f first
#define s second
using namespace std;
#include <vector>
const int N = 3e5 + 5;
int lz[4 * N], f[N];
pii MX, MN;
struct node{
    int hi, idh;
    int lo, idl;

} t[4 * N];
node merge(node a, node b) {
    node c;
    if(a.hi <= b.hi) swap(a, b);
    c.hi = a.hi, c.idh = a.idh;

    if(a.lo >= b.lo) swap(a, b);
    c.lo = a.lo, c.idl = a.idl;
    return c;
}
void build(int u,int l,int r) {
    if(l == r) {
        t[u].idl = t[u].idh = l;
        return;
    }
    int mid = (l + r) / 2;
    build(2 * u, l, mid); build(2 * u + 1, mid + 1, r);
    t[u] = merge(t[2 * u], t[2 * u + 1]);
}
void push(int u,int l,int r) {
    if(!lz[u]) return;
    t[u].lo += lz[u]; t[u].hi += lz[u];
    if(l != r) {
        lz[2 * u] += lz[u];
        lz[2 * u + 1] += lz[u];
    }
    lz[u] = 0; return;
}
void upd(int u, int st, int en, int l, int r,int v) {
    push(u, l, r);
    if(l > en || r < st) return;
    if(st <= l && r <= en) {
        if(en == 0) {
            t[u].lo = 0, t[u].hi = v;
            t[u].idl = t[u].idh = 0;
        } else {
            lz[u] = v;
            push(u, l, r);
        }
        return;
    }
    int mid = (l + r) / 2;
    upd(2 * u, st, en, l, mid, v); upd(2 * u + 1, st, en, mid + 1, r, v);
    t[u] = merge(t[2 * u], t[2 * u + 1]);
}
node get(int u, int l, int r, int v) {
    push(u, l, r);
    int mid = (l + r) / 2;
    if(l == r) {

        MX = max(MX, {t[u].hi, t[u].idh});
        MN = min(MN, {t[u].lo, t[u].idl});
        return {MX.f, MX.s, MN.f, MN.s};
    }
    push(2 * u + 1, l, mid);
    if(max(MX.f, t[2 * u + 1].hi) - min(MN.f, t[2 * u + 1].lo) >= v) return get(2 * u + 1, mid + 1, r, v);

    MX = max(MX, {t[2 * u + 1].hi, t[2 * u + 1].idh});
    MN = min(MN, {t[2 * u + 1].lo, t[2 * u + 1].idl});

    return get(2 * u, l, mid, v);
}
void upd(int id, int n, int v) {
    for(id; id <= n; id += id & (-id)) f[id] += v;
}
int get(int id) {
    int ans = 0;
    for(id; id >= 1; id -= id & (-id)) ans += f[id];
    return ans;
}
std::vector<int> distribute_candies(std::vector<int> c, std::vector<int> l,
                                    std::vector<int> r, std::vector<int> v) {
    int q = v.size(), n = c.size();
//    vector<int> v[n + 2];
    vector<int> ans(n);
    vector<int> x(n);
    build(1, 0, q);
    for(int i = 0; i < q; i++) {
        upd(1, i + 1, q, 0, q, v[i]);
        upd(i + 1, q, v[i]);
        for(int j = l[i]; j <= r[i]; j++) {
            x[j] += v[i];
            x[j] = min(x[j], c[j]);
            x[j] = max(x[j], 0);
        }
    }
    for(int i = 0; i < n; i++) {
        upd(1, 0, 0, 0, q, c[i]);
        MX = {-1, -1}; MN = {1e9,1e9};
        node x = get(1, 0, v.size(), c[i]);
        if(x.idl <= x.idh) {
            ans[i] = c[i] + get(v.size()) - get(x.idh);
        } else ans[i] = get(v.size()) - get(x.idl);
    }
    return x;
}

Compilation message

candies.cpp: In function 'void upd(int, int, int)':
candies.cpp:78:9: warning: statement has no effect [-Wunused-value]
   78 |     for(id; id <= n; id += id & (-id)) f[id] += v;
      |         ^~
candies.cpp: In function 'int get(int)':
candies.cpp:82:9: warning: statement has no effect [-Wunused-value]
   82 |     for(id; id >= 1; id -= id & (-id)) ans += f[id];
      |         ^~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 4 ms 468 KB Output is correct

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5054 ms 17276 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 304 ms 16096 KB Output is correct
3 Correct 285 ms 3836 KB Output is correct
4 Execution timed out 5046 ms 17188 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 608 ms 16040 KB Output is correct
4 Correct 711 ms 3592 KB Output is correct
5 Execution timed out 5084 ms 16744 KB Time limit exceeded
6 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 2 ms 340 KB Output is correct
5 Correct 4 ms 468 KB Output is correct
6 Execution timed out 5054 ms 17276 KB Time limit exceeded
7 Halted 0 ms 0 KB -