oj.uz

답안 #733462

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
733462 2023-04-30T20:21:39 Z benjaminkleyn 사탕 분배 (IOI21_candies) C++17
0 / 100
 2127 ms 23064 KB 
#include "candies.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int M[800000] = {0}, m[800000] = {0}, lazy[800000] = {0};

void push(int v)
{
    M[2 * v] += lazy[v];
    M[2 * v + 1] += lazy[v];

    m[2 * v] += lazy[v];
    m[2 * v + 1] += lazy[v];

    lazy[2 * v] += lazy[v];
    lazy[2 * v + 1] += lazy[v];
    lazy[v] = 0;
}

void update(int v, int tl, int tr, int l, int r, int dx)
{
    if (r < tl || tr < l)
        return;
    if (l <= tl && tr <= r)
    {
        M[v] += dx;
        m[v] += dx;
        lazy[v] += dx;
        return;
    }

    push(v);
    int tm = (tl + tr) / 2;
    update(2 * v, tl, tm, l, r, dx);
    update(2 * v + 1, tm + 1, tr, l, r, dx);
    M[v] = max(M[2 * v], M[2 * v + 1]);
    m[v] = min(m[2 * v], m[2 * v + 1]);
}

int Max(int v, int tl, int tr, int l, int r)
{
    if (r < tl || tr < l)
        return INT_MIN;
    if (l <= tl && tr <= r)
        return M[v];

    push(v);
    int tm = (tl + tr) / 2;
    return max(
        Max(2 * v, tl, tm, l, r),
        Max(2 * v + 1, tm + 1, tr, l, r)
    );
}

int Min(int v, int tl, int tr, int l, int r)
{
    if (r < tl || tr < l)
        return INT_MAX;
    if (l <= tl && tr <= r)
        return m[v];

    push(v);
    int tm = (tl + tr) / 2;
    return min(
        Min(2 * v, tl, tm, l, r),
        Min(2 * v + 1, tm + 1, tr, l, r)
    );
}

int query(int c, int q)
{
    int lo = 0, hi = q + 1;
    while (lo < hi)
    {
        int mid = (lo + hi) / 2;
        if (Max(1, 0, q + 1, mid, q + 1) - Min(1, 0, q + 1, mid + 1, q + 1) > c)
            lo = mid + 1;
        else
            hi = mid;
    }
    int ans1 = lo;

    lo = 0, hi = q + 1;
    while (lo < hi)
    {
        int mid = (lo + hi) / 2;
        if (Max(1, 0, q + 1, mid + 1, q + 1) - Min(1, 0, q + 1, mid, q + 1) > c)
            lo = mid + 1;
        else
            hi = mid;
    }
    int ans2 = lo;
    if (ans1 > ans2)
        return Max(1, 0, q + 1, ans1, q + 1) - Max(1, 0, q + 1, q + 1, q + 1);
    else
        return c - (Max(1, 0, q + 1, ans2, q + 1) - Max(1, 0, q + 1, q + 1, q + 1));
}

struct Event
{
    int idx, val, time;
};
bool operator<(const Event &A, const Event &B)
{
    return A.idx < B.idx;
}

vector<int> distribute_candies(vector<int> c, vector<int> l, vector<int> r, vector<int> v) 
{
    int n = c.size(), q = v.size();

    vector<Event> events;
    events.push_back({-1, 1000000000, -1});
    events.push_back({-2, -1000000000, -2});
    for (int i = 0; i < q; i++)
    {
        events.push_back({l[i], v[i], i});
        events.push_back({r[i] + 1, -v[i], i});
    }
    sort(events.begin(), events.end());
    vector<int> s(n);
    int j = 0, sum = 0;
    for (int i = 0; i < n; i++)
    {
        while (j < events.size() && events[j].idx <= i)
        {
            sum += events[j].val;
            update(1, 0, q + 1, events[j].time + 2, q + 1, events[j].val);
            j++;
        }
        s[i] = query(c[i], q);
    }

    return s;
}

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:126:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  126 |         while (j < events.size() && events[j].idx <= i)
      |                ~~^~~~~~~~~~~~~~~

Subtask #1
0 / 3.0

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

Subtask #2
0 / 8.0

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

Subtask #3
0 / 27.0

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

Subtask #4
0 / 29.0

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

Subtask #5
0 / 33.0

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