oj.uz

답안 #596118

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
596118 2022-07-14T11:52:06 Z keta_tsimakuridze 사탕 분배 (IOI21_candies) C++17
0 / 100
 110 ms 49832 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];
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;
}
int 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);
    }
    for(int i = 0; i < n; i++) {
        upd(1, 0, 0, 0, q, c[i]);
        MX = {-1, -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] = get(v.size()) - get(x.idl);
    }
    return ans;
}

Compilation message

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

Subtask #1
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 110 ms 49832 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 468 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 212 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Runtime error 1 ms 468 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -