Submission #596136

#	Time	Username	Problem	Language	Result	Execution time	Memory
596136		keta_tsimakuridze	Distributing Candies (IOI21_candies)	C++17	100 / 100	556 ms	58976 KiB

candies

#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 (stderr)

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 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 29 / 29
• Subtask 5: 33 / 33