Submission #1058469

#	Time	Username	Problem	Language	Result	Execution time	Memory
1058469		vjudge1	Distributing Candies (IOI21_candies)	C++17	0 / 100	5094 ms	23132 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;
    AINT(int N) : n(N), Mi(4 * N, 0), Ma(4 * N, 0), Lz(4 * N, 0) {}

    void prop(int u, int s, int d) {
        if(!Lz[u]) return;
        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] == 0 && v < 0) {
                return;
            }
            if(Mi[u] == C && v > 0) {
                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;
}

Compilation message (stderr)

candies.cpp: In function 'vi distribute_candies(vi, vi, vi, vi)':
candies.cpp:76:10: warning: variable 'all_poz' set but not used [-Wunused-but-set-variable]
   76 |     bool all_poz = true;
      |          ^~~~~~~

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