oj.uz

Submission #625476

# Submission time Handle Problem Language Result Execution time Memory
625476 2022-08-10T12:59:14 Z MohamedFaresNebili Distributing Candies (IOI21_candies) C++17
27 / 100
 939 ms 21276 KB 
#include <bits/stdc++.h>
#include "candies.h"
#pragma GCC optimize ("Ofast")
#pragma GCC target ("avx2")
/// #pragma GCC optimize("unroll-loops")

            using namespace std;

            using ll = long long;
            using ld = long double;

            #define ff first
            #define ss second
            #define pb push_back
            #define all(x) (x).begin(), (x).end()
            #define lb lower_bound

            const int MOD = 998244353;
            const int nx[4] = {-1, 0, 1, 0}, ny[4] = {0, 1, 0, -1};

            int mn[800005], mx[800005], lazy[800005];
            bool umn[800005], umx[800005];

            void prop(int v, int l, int r) {
                if(l == r) return;
                mn[v * 2] += lazy[v]; mx[v * 2] += lazy[v]; lazy[v * 2] += lazy[v];
                mn[v * 2 + 1] += lazy[v]; mx[v * 2 + 1] += lazy[v]; lazy[v * 2 + 1] += lazy[v];

                if(umn[v]) {
                    mn[v * 2] = min(mn[v * 2], mx[v]);
                    mn[v * 2 + 1] = min(mn[v * 2 + 1], mx[v]);

                    mx[v * 2] = min(mx[v * 2], mx[v]);
                    mx[v * 2 + 1] = min(mx[v * 2 + 1], mx[v]);

                    umn[v * 2] = umn[v * 2 + 1] = 1;
                }

                if(umx[v]) {
                    mn[v * 2] = max(mn[v * 2], mn[v]);
                    mn[v * 2 + 1] = max(mn[v * 2 + 1], mn[v]);

                    mx[v * 2] = max(mx[v * 2], mn[v]);
                    mx[v * 2 + 1] = max(mx[v * 2 + 1], mn[v]);

                    umx[v * 2] = umx[v * 2 + 1] = 1;
                }

                lazy[v] = umn[v] = umx[v] = 0;
            }
            void update(int v, int l, int r, int lo, int hi, int val) {
                prop(v, l, r);
                if(l > hi || r < lo) return;
                if(l >= lo && r <= hi) {
                    mn[v] += val; mx[v] += val; lazy[v] += val;
                    return;
                }
                update(v * 2, l, (l + r) / 2, lo, hi, val);
                update(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, val);
                mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
                mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
            }
            void umin(int v, int l, int r, int lo, int hi, int val) {
                prop(v, l, r);
                if(l > hi || r < lo) return;
                if(l >= lo && r <= hi) {
                    mn[v] = min(mn[v], val);
                    mx[v] = min(mx[v], val);
                    umn[v] = 1;
                    return;
                }
                umin(v * 2, l, (l + r) / 2, lo, hi, val);
                umin(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, val);
                mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
                mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
            }
            void umax(int v, int l, int r, int lo, int hi, int val) {
                prop(v, l, r);
                if(l > hi || r < lo) return;
                if(l >= lo && r <= hi) {
                    mn[v] = max(mn[v], val);
                    mx[v] = max(mx[v], val);
                    umx[v] = 1;
                    return;
                }
                umax(v * 2, l, (l + r) / 2, lo, hi, val);
                umax(v * 2 + 1, (l + r) / 2 + 1, r, lo, hi, val);
                mn[v] = min(mn[v * 2], mn[v * 2 + 1]);
                mx[v] = max(mx[v * 2], mx[v * 2 + 1]);
            }
            int query(int v, int l, int r, int p) {
                prop(v, l, r);
                if(l == r) return mn[v];
                int md = (l + r) / 2;
                if(p <= md) return query(v * 2, l, md, p);
                return query(v * 2 + 1, md + 1, r, p);
            }

            vector<int> distribute_candies(vector<int> c, vector<int> l,
                                           vector<int> r, vector<int> v) {
                int N = c.size(), Q = l.size();
                for(int i = 0; i < Q; i++) {
                    int x = l[i], y = r[i], add = v[i];
                    update(1, 0, N - 1, x, y, add);
                    umin(1, 0, N - 1, x, y, c[0]);
                    umax(1, 0, N - 1, x, y, 0);
                }
                vector<int> res(N);
                for(int i = 0; i < N; i++)
                    res[i] = query(1, 0, N - 1, i);
                return res;
            }

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

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

Subtask #3
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 316 KB Output is correct
2 Correct 411 ms 8036 KB Output is correct
3 Correct 117 ms 13112 KB Output is correct
4 Correct 928 ms 20480 KB Output is correct
5 Correct 847 ms 20832 KB Output is correct
6 Correct 848 ms 21276 KB Output is correct
7 Correct 868 ms 20588 KB Output is correct

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 340 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 212 KB Output is correct
2 Incorrect 1 ms 316 KB Output isn't correct
3 Halted 0 ms 0 KB -