제출 #1058565

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1058565		vjudge1	사탕 분배 (IOI21_candies)	C++17	38 / 100	349 ms	26584 KiB

candies

#include "candies.h"

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using vi = vector<int>;
using vll = vector<ll>;

int C;

struct AINT {
    int n;
    vi Mi, Ma, Lz;
    vi LzSet0, LzSet1;
    AINT(int N) : n(N), Mi(4 * N, 0), Ma(4 * N, 0), Lz(4 * N, 0), LzSet0(4 * N, 0), LzSet1(4 * N, 0) {}

    void prop0(int u, int s, int d) {
        if(LzSet0[u]) {
            Mi[u] = Ma[u] = Lz[u] = 0;
            if(s != d) {
                LzSet0[u << 1] = 1;
                LzSet1[u << 1] = 0;
                LzSet0[u << 1 | 1] = 1;
                LzSet1[u << 1 | 1] = 0;
            }
            LzSet0[u] = 0;
        }
        if(LzSet1[u]) {
            Mi[u] = Ma[u] = C;
            Lz[u] = 0;
            if(s != d) {
                LzSet0[u << 1] = 0;
                LzSet1[u << 1] = 1;
                LzSet0[u << 1 | 1] = 0;
                LzSet1[u << 1 | 1] = 1;
            }
            LzSet1[u] = 0;
        }
    }
    void prop(int u, int s, int d) {
        prop0(u, s, d);

        if(Lz[u]) {
            if(s != d) {
                prop0(u << 1, s, (s + d) >> 1);
                prop0(u << 1 | 1, ((s + d) >> 1) + 1, d);
            }
            Ma[u] += Lz[u];
            Mi[u] += Lz[u];
            Mi[u] = max(Mi[u], 0);
            Ma[u] = max(Ma[u], 0);
            Ma[u] = min(Ma[u], C);
            Mi[u] = min(Mi[u], C);
            if(s != d) {
                Lz[u << 1] += Lz[u];
                Lz[u << 1 | 1] += Lz[u];
            }
            Lz[u] = 0;
        }
    }
    
    void update(int l, int r, int v, int u, int s, int d) {
        prop(u, s, d);
        if(r < s || d < l) return;
        if(l <= s && d <= r) {
            if(Ma[u] + v <= C && Mi[u] + v >= 0) {
                Lz[u] += v;
                prop(u, s, d);
                return;
            }
            if(Ma[u] + v <= 0) {
                LzSet0[u] = 1;
                prop(u, s, d);
                return;
            }
            if(Mi[u] + v >= C) {
                LzSet1[u] = 1;
                prop(u, s, d);
                return;
            }
            if(s == d) {
                Lz[u] += v;
                prop(u, s, d);
                return;
            }
        }
        update(l, r, v, u << 1, s, (s + d) >> 1);
        update(l, r, v, u << 1 | 1, ((s + d) >> 1) + 1, d);
        Mi[u] = min(Mi[u << 1], Mi[u << 1 | 1]);
        Ma[u] = max(Ma[u << 1], Ma[u << 1 | 1]);
    }

    void update(int l, int r, int v) {
        update(l, r, v, 1, 0, n - 1);
    }

    int query(int p, int u, int s, int d) {
        prop(u, s, d);
        if(s == d) return Ma[u];
        int mij = (s + d) / 2;
        if(p <= mij) return query(p, u << 1, s, mij);
        return query(p, u << 1 | 1, mij + 1, d);
    }

    int query(int p) { return query(p, 1, 0, n - 1); }
};

vi distribute_candies(vi c, vi l, vi r, vi v) {
    int n = c.size(), q = l.size();
    bool all_poz = true;
    for(auto it : v)
        if(it < 0) all_poz = false;
    if(n <= 2000 && q <= 2000) {
        vi A(n, 0);
        for(int i = 0; i < q; ++i) {
            for(int j = l[i]; j <= r[i]; ++j) {
                A[j] += v[i];
                A[j] = max(A[j], 0);
                A[j] = min(A[j], c[j]);
            }
        }
        return A;
    }
    if(all_poz) {
        vll S(n, 0);
        for(int i = 0; i < q; ++i) {
            S[l[i]] += v[i];
            if(r[i] + 1 < n) S[r[i] + 1] -= v[i];
        }
        for(int i = 1; i < n; ++i) {
            S[i] = S[i] + S[i - 1];
        }
        vi Re(n, 0);
        for(int i = 0; i < n; ++i) {
            Re[i] = min(S[i], (ll)c[i]);
        }
        return Re;
    }
    /// presupun ca c e acelasi
    C = c[0];
    AINT Sol(n);
    for(int i = 0; i < q; ++i) {
        Sol.update(l[i], r[i], v[i]);
    }
    vi Re(n);
    for(int i = 0; i < n; ++i) {
        Re[i] = Sol.query(i);
    }
    return Re;
}

• Subtask 1: 3 / 3
• Subtask 2: 8 / 8
• Subtask 3: 27 / 27
• Subtask 4: 0 / 29
• Subtask 5: 0 / 33