Submission #579036

#	Time	Username	Problem	Language	Result	Execution time	Memory
579036		fvogel499	Distributing Candies (IOI21_candies)	C++17	29 / 100	1403 ms	38744 KiB

candies

/*
 * File created on 06/18/2022 at 11:23:40.
 * Link to problem: 
 * Description: subtask 4 solution
 * Time complexity: O(N log^2 N)
 * Space complexity: O()
 * Status: ---
 * Copyright: Ⓒ 2022 Francois Vogel
*/

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

#define pii pair<int, int>
#define f first
#define s second

#define vi vector<int>
#define all(x) x.begin(), x.end()
#define size(x) (int)((x).size())
#define pb push_back
#define ins insert
#define cls clear

#define ll long long
#define ld long double

typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;

const int p2 = 1<<18;

struct Segtree {
    Segtree() {
        lzSet = new bool [p2*2];
        for (int i = 0; i < p2*2; i++) lzSet[i] = false;
        t = new int [p2*2];
        for (int i = 0; i < p2*2; i++) t[i] = 0;
        lzAdd = new int [p2*2];
        for (int i = 0; i < p2*2; i++) lzAdd[i] = 0;
    }
    void push(int qn) {
        if (lzSet[qn]) {
            if (qn < p2) {
                lzAdd[qn*2] = lzAdd[qn*2+1] = false;
                lzSet[qn*2] = lzSet[qn*2+1] = true;
            }
            t[qn] = 0;
            lzSet[qn] = false;
        }
        if (lzAdd[qn]) {
            if (qn < p2) {
                lzAdd[qn*2] += lzAdd[qn];
                lzAdd[qn*2+1] += lzAdd[qn];
            }
            t[qn] += lzAdd[qn];
            lzAdd[qn] = 0;
        }
    }
    void set(int rb, int re, int qn = 1, int qb = 0, int qe = p2-1) {
        push(qn);
        if (rb > qe || qb > re) return;
        else if (rb <= qb && qe <= re) {
            lzSet[qn] = true;
        }
        else {
            int qm = (qb+qe)/2;
            set(rb, re, qn*2, qb, qm);
            set(rb, re, qn*2+1, qm+1, qe);
        }
    }
    void add(int rb, int re, int rv, int qn = 1, int qb = 0, int qe = p2-1) {
        push(qn);
        if (rb > qe || qb > re) return;
        else if (rb <= qb && qe <= re) {
            lzAdd[qn] += rv;
        }
        else {
            int qm = (qb+qe)/2;
            add(rb, re, rv, qn*2, qb, qm);
            add(rb, re, rv, qn*2+1, qm+1, qe);
        }
    }
    int get(int r, int qn = 1, int qb = 0, int qe = p2-1) {
        push(qn);
        if (r == qb && r == qe) return t[qn];
        else {
            int qm = (qb+qe)/2;
            if (r <= qm) return get(r, qn*2, qb, qm);
            else return get(r, qn*2+1, qm+1, qe);
        }
    }
    bool* lzSet;
    int* t, *lzAdd;
};

vi distribute_candies(vi b, vi queryL, vi queryR, vi queryV) {
    int n = size(b);
    int nbQ = size(queryL);
    vector<pii> sorted;
    for (int i = 0; i < n; i++) sorted.pb({b[i], i});
    sort(all(sorted));
    int posOf [n];
    for (int i = 0; i < n; i++) posOf[sorted[i].s] = i;
    for (int i = 0; i < n; i++) b[i] = sorted[i].f;
    Segtree st [2];
    st[0] = Segtree();
    st[1] = Segtree();
    Segtree use = Segtree();
    for (int i : queryV) {
        if (i == 0) continue;
        int upto = -1;
        for (int j = p2; j; j /= 2) if (upto+j < n) {
            int loc;
            if (use.get(upto+j) == 0) {
                loc = st[0].get(upto+j);
                loc += i;
            }
            else {
                loc = st[1].get(upto+j);
                loc = b[upto+j] - loc;
                loc += i;
            }
            if (!(0 <= loc && loc <= b[upto+j])) {
                upto += j;
            }
        }
        st[0].add(0, n-1, i);
        st[1].add(0, n-1, -i);
        if (upto >= 0) {
            if (i < 0) {
                st[0].set(0, upto);
                use.set(0, upto);
            }
            else {
                st[1].set(0, upto);
                use.set(0, upto);
                use.add(0, upto, 1);
            }
        }
        // for debug
        // for (int j = 0; j < n; j++) {
        //     cout << use.get(j) << ' ';
        // }
        // cout << endl;
        // int d = 0;
        // d++;
        // end debug
        // for debugging purposes
        // for (int j = 0; j < n; j++) {
        //     int res;
        //     if (use.get(j) == 0) {
        //         res = st[0].get(j);
        //     }
        //     else {
        //         res = st[1].get(j);
        //         res = b[j]-res;
        //     }
        //     // assert(0 <= res && res <= b[j]);
        //     cout << res << ' ';
        // }
        // cout << endl;
        // int d2 = 0;
        // d2++;
        // end debugging
    }
    vi ans;
    for (int i = 0; i < n; i++) {
        int res;
        if (use.get(posOf[i]) == 0) {
            res = st[0].get(posOf[i]);
        }
        else {
            res = st[1].get(posOf[i]);
            res = b[posOf[i]]-res;
        }
        // assert(0 <= res && res <= b[posOf[i]]);
        ans.pb(res);
    }
    return ans;
}

// signed main() {
//     cin.tie(0);
//     ios_base::sync_with_stdio(0);

//     mt19937 rng(chrono::high_resolution_clock::now().time_since_epoch().count());

//     distribute_candies({0, 4}, {}, {}, {9, -3});

//     while (1) {
//         int n = 5;
//         int nbQ = 10;
//         int lim = 1e9;
//         vi b, q;
//         for (int i = 0; i < n; i++) {
//             b.pb(rng()%lim);
//         }
//         for (int i = 0; i < nbQ; i++) q.pb((-lim)+rng()%(2*lim));
//         vi ans = distribute_candies(b, q, q, q);
//         vi exp(n, 0);
//         for (int i : q) {
//             for (int j = 0; j < n; j++) {
//                 exp[j] += i;
//                 exp[j] = max(exp[j], 0);
//                 exp[j] = min(exp[j], b[j]);
//             }
//         }
//         for (int i = 0; i < n; i++) {
//             if (ans[i] != exp[i]) {
//                 cout << "WA" << endl;
//                 cout << "b: ";
//                 for (int j : b) cout << j << ' ';
//                 cout << endl;
//                 cout << "q: ";
//                 for (int j : q) cout << j << ' ';
//                 cout << endl;
//                 cout << "ans: ";
//                 for (int j : ans) cout << j << ' ';
//                 cout << endl;
//                 cout << "exp: ";
//                 for (int j : exp) cout << j << ' ';
//                 cout << endl;
//                 return 0;
//             }
//         }
//     }

//     cout.flush();
//     int d = 0;
//     d++;
// }

Compilation message (stderr)

candies.cpp: In function 'std::vector<int> distribute_candies(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
candies.cpp:103:9: warning: unused variable 'nbQ' [-Wunused-variable]
  103 |     int nbQ = size(queryL);
      |         ^~~

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