oj.uz

Submission #1058469

# Submission time Handle Problem Language Result Execution time Memory
1058469 2024-08-14T10:09:06 Z vjudge1 Distributing Candies (IOI21_candies) C++17
0 / 100
 5000 ms 23132 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 146 ms 16724 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 89 ms 5212 KB Output is correct
3 Correct 68 ms 14164 KB Output is correct
4 Correct 517 ms 22608 KB Output is correct
5 Correct 1079 ms 23132 KB Output is correct
6 Execution timed out 5094 ms 22608 KB Time limit exceeded
7 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Incorrect 0 ms 348 KB Output isn't correct
3 Halted 0 ms 0 KB -