oj.uz

Submission #831850

# Submission time Handle Problem Language Result Execution time Memory
831850 2023-08-20T16:04:21 Z haxorman Distributing Candies (IOI21_candies) C++17
0 / 100
 5000 ms 10460 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 = 2) {
    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);
        }
    }
    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();
    
    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;
    vector<int> ans(n);
    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:127:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  127 |     for (int i = 0; i < calc.size(); ++i) {
      |                     ~~^~~~~~~~~~~~~

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

# Verdict Execution time Memory Grader output
1 Execution timed out 5052 ms 10460 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

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

Subtask #4
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 3752 KB Output is correct
2 Correct 1259 ms 3764 KB Output is correct
3 Execution timed out 5062 ms 9080 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #5
0 / 33.0

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