oj.uz

답안 #832029

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
832029 2023-08-20T21:01:02 Z haxorman 사탕 분배 (IOI21_candies) C++17
40 / 100
 532 ms 16512 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;

#define f first
#define s second

const int mxN = 2e5 + 7;
const int SZ = exp2(ceil(log2(mxN)));

pair<pair<int,int>,int> seg[5 * mxN];
int lazy[5 * mxN], n, q, len;

void push(int ind, int l, int r, int cnt = 1) {
    seg[ind].f.f += lazy[ind], seg[ind].f.s += lazy[ind];

    if (l != r) {
        lazy[2 * ind] += lazy[ind];
        lazy[2 * ind + 1] += lazy[ind];
        
        if (cnt) {
            int mid = (l + r) / 2;
            push(2 * ind, l, mid, cnt - 1);
            push(2 * ind + 1, mid + 1, r, cnt - 1);
        }
    }
    lazy[ind] = 0;
}

void update(int lo, int hi, int val, int ind = 1, int l = 0, int r = SZ - 1) {
    push(ind, l, r);
    if (lo > r || l > hi) {
        return;
    }

    if (lo <= l && r <= hi) {
        push(ind, l, r);
        lazy[ind] += val;
        if (l == r) {
            seg[ind].s = l;
        }
        push(ind, l, r);
        return;
    }

    int mid = (l + r) / 2;
    update(lo, hi, val, 2 * ind, l, mid);
    push(ind, l, r);
    update(lo, hi, val, 2 * ind + 1, mid + 1, r);
    push(ind, l, r);

    seg[ind].f.f = min(seg[2 * ind].f.f, seg[2 * ind + 1].f.f);
    seg[ind].f.s = max(seg[2 * ind].f.s, seg[2 * ind + 1].f.s);
    push(ind, l, r);
}

int query(int pos, int ind = 1, int l = 0, int r = SZ - 1) {
    push(ind, l, r);
    if (l == r) {
        return seg[ind].f.f;
    }

    int mid = (l + r) / 2;
    if (pos <= mid) {
        return query(pos, 2 * ind, l, mid);
    }
    else {
        return query(pos, 2 * ind + 1, mid + 1, r);
    }
}

int walk(int lo, int val, bool t, int ind = 1, int l = 0, int r = SZ - 1) {
    push(ind, l, r);
    if (lo > r || (t && seg[ind].f.s <= val) || (!t && seg[ind].f.f >= val)) {
        return (t ? INT_MIN : INT_MAX);
    }
    
    if (l == r) {
        if (t) {
            update(l, len, -seg[ind].f.s + val);
        }
        else {
            update(l, len, -seg[ind].f.f);
        }
        push(ind, l, r);
        return seg[ind].s;
    }
    
    int mid = (l + r) / 2;
    if (l >= lo) {
        push(ind, l, r);
        if ((t && seg[2*ind].f.s > val) || (!t && seg[2*ind].f.f < val)) {
            return walk(lo, val, t, 2 * ind, l, mid);
        }
        else {
            return walk(lo, val, t, 2 * ind + 1, mid + 1, r);
        }
    }

    push(ind, l, r);
    int res = walk(lo, val, t, 2 * ind, l, mid);
    push(ind, l, r);
    if (res == INT_MIN || res == INT_MAX) {
        res = walk(lo, val, t, 2 * ind + 1, mid + 1, r);
        push(ind, l, r);
    }
    return res;
}

vector<int> distribute_candies(vector<int> c, vector<int> l,
                                    vector<int> r, vector<int> v) {
    n = c.size(), q = v.size();
    
    bool sbt2 = true;
    for (int i = 0; i < q; ++i) {
        if (v[i] <= 0) {
            sbt2 = false;
        }
    }

    vector<int> ans(n);
    if (n <= 2000 && q <= 2000) {
        for (int i = 0; i < q; ++i) {
            for (int j = l[i]; j <= r[i]; ++j) {
                ans[j] += v[i];

                ans[j] = max(ans[j], 0);
                ans[j] = min(ans[j], c[j]);
            }
        }
    }
    else if (sbt2) {
        vector<long long> pref(n + 1);
        for (int i = 0; i < q; ++i) {
            pref[r[i] + 1] -= v[i];
            pref[l[i]] += v[i];
        }

        for (int i = 0; i < n; ++i) {
            if (i) {
                pref[i] += pref[i - 1];
            }
            ans[i] = min((long long) c[i], pref[i]);
        }
    }
    else {
        int cur = 0;
        vector<int> calc;
        for (int i = 0; i < q; ++i) {
            cur += v[i];
            calc.push_back(cur);

            if (cur <= 0) {
                cur = 0;
                calc.clear();
            }
        }

        len = calc.size();
        for (int i = 0; i < calc.size(); ++i) {
            update(i + 1, i + 1, calc[i]);
        }

        vector<pair<int,int>> arr;
        for (int i = 0; i < n; ++i) {
            arr.push_back({c[i], i});
        }
        sort(arr.begin(), arr.end(), greater<pair<int,int>>());

        int ind = 1;
        for (int i = 0; i < n; ++i) {
            while (walk(ind, arr[i].f, 1) != INT_MIN) {
                int nex = walk(ind, 0, 0);
                if (nex != INT_MAX) {
                    ind = nex + 1;
                }
            }

            ans[arr[i].s] = query(len);
        }
    }
     


    return ans;
}

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:160:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  160 |         for (int i = 0; i < calc.size(); ++i) {
      |                         ~~^~~~~~~~~~~~~

Subtask #1
3.0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 380 KB Output is correct

Subtask #2
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 82 ms 8816 KB Output is correct
2 Correct 78 ms 12912 KB Output is correct
3 Correct 82 ms 12728 KB Output is correct

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 212 KB Output is correct
2 Incorrect 273 ms 12260 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
29.0 / 29.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 60 ms 5796 KB Output is correct
4 Correct 284 ms 4928 KB Output is correct
5 Correct 532 ms 16512 KB Output is correct
6 Correct 414 ms 12172 KB Output is correct
7 Correct 518 ms 9664 KB Output is correct
8 Correct 476 ms 15584 KB Output is correct
9 Correct 79 ms 8908 KB Output is correct

Subtask #5
0 / 33.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 3 ms 380 KB Output is correct
6 Correct 82 ms 8816 KB Output is correct
7 Correct 78 ms 12912 KB Output is correct
8 Correct 82 ms 12728 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Incorrect 273 ms 12260 KB Output isn't correct
11 Halted 0 ms 0 KB -