oj.uz

답안 #579016

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
579016 2022-06-18T09:53:34 Z fvogel499 사탕 분배 (IOI21_candies) C++17
0 / 100
 626 ms 68052 KB 
/*
 * 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));
    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 (i < 0) {
            st[0].set(0, upto);
            use.set(0, upto, 0);
        }
        else {
            st[1].set(0, upto);
            use.set(0, upto, 0);
            use.add(0, upto, 1);
        }
        //
        // for (int j = 0; j < n; j++) {
        //     int res;
        //     if (use[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 d = 0;
        // d++;
        //
    }
    vi ans;
    for (pii x : sorted) {
        int i = x.s;
        int res;
        if (use.get(i) == 0) {
            res = st[0].get(i);
        }
        else {
            res = st[1].get(i);
            res = b[i]-res;
        }
        assert(0 <= res && res <= x.f);
        ans.pb(res);
    }
    return ans;
}

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

//     vi a = distribute_candies({5, 9, 12, 29, 56}, {}, {}, {+7, +6, -12, +4});
//     for (int i : a) cout << i << " ";

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

Compilation message

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

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 23340 KB Output is correct
2 Runtime error 35 ms 47360 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -

Subtask #2
0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 626 ms 68052 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 10 ms 23380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 32 ms 47312 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 10 ms 23340 KB Output is correct
2 Runtime error 35 ms 47360 KB Execution killed with signal 6
3 Halted 0 ms 0 KB -