oj.uz

Submission #596136

# Submission time Handle Problem Language Result Execution time Memory
596136 2022-07-14T12:08:27 Z keta_tsimakuridze Distributing Candies (IOI21_candies) C++17
100 / 100
 556 ms 58976 KB 
#include "candies.h"
#include<bits/stdc++.h>

#define f first
#define s second
#define ll long long
#define pii pair<ll,ll>
using namespace std;
#include <vector>
const int N = 3e5 + 5;
const ll inf = 1e18;
ll lz[4 * N], f[N];
vector<pair<int,int> > st[N], en[N];
pii MX, MN;
struct node{
    ll hi, idh;
    ll 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;
}
ll get(int id) {
    ll 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]);
   //     assert(l[i] == 0 && r[i] == n - 1);
        st[l[i]].push_back({i + 1, v[i]});
        en[r[i] + 1].push_back({i + 1, -v[i]});
    }
    for(int i = 0; i < n; i++) {
        for(int x = 0; x < st[i].size(); x++) {
            upd(1, st[i][x].f, q, 0, q, st[i][x].s);
            upd(st[i][x].f, q, st[i][x].s);
        }
        for(int x = 0; x < en[i].size(); x++) {
            upd(1, en[i][x].f, q, 0, q, en[i][x].s);
            upd(en[i][x].f, q, en[i][x].s);
        }
        upd(1, 0, 0, 0, q, c[i]);
        MX = {-inf, -1}; MN = {inf, 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] = (ll)(get(v.size()) - get(x.idl));
    }
    return ans;
}

Compilation message

candies.cpp: In function 'void upd(int, int, int)':
candies.cpp:82:9: warning: statement has no effect [-Wunused-value]
   82 |     for(id; id <= n; id += id & (-id)) f[id] += v;
      |         ^~
candies.cpp: In function 'long long int get(int)':
candies.cpp:86:9: warning: statement has no effect [-Wunused-value]
   86 |     for(id; id >= 1; id -= id & (-id)) ans += f[id];
      |         ^~
candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:104:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |         for(int x = 0; x < st[i].size(); x++) {
      |                        ~~^~~~~~~~~~~~~~
candies.cpp:108:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  108 |         for(int x = 0; x < en[i].size(); x++) {
      |                        ~~^~~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 8 ms 14676 KB Output is correct
4 Correct 9 ms 14676 KB Output is correct
5 Correct 10 ms 14708 KB Output is correct

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 490 ms 52232 KB Output is correct
2 Correct 493 ms 52352 KB Output is correct
3 Correct 510 ms 52276 KB Output is correct

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 293 ms 46724 KB Output is correct
3 Correct 97 ms 18236 KB Output is correct
4 Correct 494 ms 52360 KB Output is correct
5 Correct 525 ms 58580 KB Output is correct
6 Correct 517 ms 58976 KB Output is correct
7 Correct 471 ms 58312 KB Output is correct

Subtask #4
29.0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 14292 KB Output is correct
2 Correct 9 ms 14416 KB Output is correct
3 Correct 164 ms 44500 KB Output is correct
4 Correct 98 ms 17760 KB Output is correct
5 Correct 239 ms 47716 KB Output is correct
6 Correct 245 ms 47836 KB Output is correct
7 Correct 238 ms 47608 KB Output is correct
8 Correct 242 ms 47588 KB Output is correct
9 Correct 230 ms 47684 KB Output is correct

Subtask #5
33.0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14420 KB Output is correct
2 Correct 7 ms 14420 KB Output is correct
3 Correct 8 ms 14676 KB Output is correct
4 Correct 9 ms 14676 KB Output is correct
5 Correct 10 ms 14708 KB Output is correct
6 Correct 490 ms 52232 KB Output is correct
7 Correct 493 ms 52352 KB Output is correct
8 Correct 510 ms 52276 KB Output is correct
9 Correct 7 ms 14420 KB Output is correct
10 Correct 293 ms 46724 KB Output is correct
11 Correct 97 ms 18236 KB Output is correct
12 Correct 494 ms 52360 KB Output is correct
13 Correct 525 ms 58580 KB Output is correct
14 Correct 517 ms 58976 KB Output is correct
15 Correct 471 ms 58312 KB Output is correct
16 Correct 8 ms 14292 KB Output is correct
17 Correct 9 ms 14416 KB Output is correct
18 Correct 164 ms 44500 KB Output is correct
19 Correct 98 ms 17760 KB Output is correct
20 Correct 239 ms 47716 KB Output is correct
21 Correct 245 ms 47836 KB Output is correct
22 Correct 238 ms 47608 KB Output is correct
23 Correct 242 ms 47588 KB Output is correct
24 Correct 230 ms 47684 KB Output is correct
25 Correct 7 ms 14412 KB Output is correct
26 Correct 101 ms 19020 KB Output is correct
27 Correct 306 ms 49420 KB Output is correct
28 Correct 556 ms 56784 KB Output is correct
29 Correct 520 ms 57216 KB Output is correct
30 Correct 531 ms 57296 KB Output is correct
31 Correct 516 ms 57604 KB Output is correct
32 Correct 510 ms 57980 KB Output is correct