제출 #800639

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
800639		_martynas	Distributing Candies (IOI21_candies)	C++17	100 / 100	1233 ms	50820 KiB

candies

#include "candies.h"
#include <vector>
#include <algorithm>
#include <cassert>
#include <iostream>
#include <cstdio>

using namespace std;

#warning change mxn back
const int mxn = 2e5+5;
using ll = long long;

const ll inf = 2e18;
const ll smaller_inf = 1e18;


struct Node {
    ll mx = -inf, mn = inf;
    int mxi = -100, mni = -100;
    ll tag = 0;
    Node() {}
    Node(int i) {
        mx = mn = 0;
        mxi = mni = i;
    }
    Node join(Node rhs) {
        Node lhs = *this;
        lhs.tag = 0;
        if(rhs.mx > lhs.mx) {
            lhs.mx = rhs.mx;
            lhs.mxi = rhs.mxi;
        }
        if(rhs.mn < mn) {
            lhs.mn = rhs.mn;
            lhs.mni = rhs.mni;
        }
        return lhs;
    }
};

int n, q;

struct Seg {
private:
    Node A[4*mxn];
    void inc_tag(int u, ll inc) {
        A[u].tag += inc;
        A[u].mx += inc, A[u].mn += inc;
    }

    void build(int u, int l, int r) {
        if(l == r) {
            A[u] = Node(l);
            return;
        }
        int m = (l+r+4)/2-2;
        build(2*u, l, m), build(2*u+1, m+1, r);
        pull(u);
    }

    void push(int u) {
        inc_tag(2*u, A[u].tag);
        inc_tag(2*u+1, A[u].tag);
        A[u].tag = 0;
    }

    void pull(int u) {
        A[u] = A[2*u].join(A[2*u+1]);
    }

    void range_add(int u, int l, int r, int ql, int qr, ll val) {
        if(qr < l || ql > r) return;
        if(ql <= l && r <= qr) {
            inc_tag(u, val);
            return;
        }
        push(u);
        int m = (l+r+4)/2-2;
        range_add(2*u, l, m, ql, qr, val);
        range_add(2*u+1, m+1, r, ql, qr, val);
        pull(u);
    }

    Node get(int u, int l, int r, int ql, int qr) {
        if(qr < l || ql > r) return Node{};
        if(ql <= l && r <= qr) {
            return A[u];
        }
        push(u);
        int m = (l+r+4)/2-2;
        return get(2*u, l, m, ql, qr).join(get(2*u+1, m+1, r, ql, qr));
    }

public:
    void build() {
        build(1, -2, q-1);
    }
    void range_add(int l, int r, ll val) {
        range_add(1, -2, q-1, l, r, val);
    }

    Node get(int l, int r) {
        return get(1, -2, q-1, l, r);
    }
};

vector<int> distribute_candies(vector<int> c, vector<int> l,
                                    vector<int> r, vector<int> v) {
    n = c.size();
    q = l.size();
    vector<int> s(n);
    struct Event {
        int t, delta;
    };
    vector<vector<Event>> events(n);
    for(int i = 0; i < q; i++) {
        events[l[i]].push_back(Event{i, v[i]});
        if(r[i] < n-1)
            events[r[i]+1].push_back(Event{i, -v[i]});
    }
    Seg seg;
    seg.build();
    seg.range_add(-2, q-1, smaller_inf);
    seg.range_add(-1, q-1, -smaller_inf);
    for(int i = 0; i < n; i++) {
        for(auto e : events[i]) {
            seg.range_add(e.t, q, e.delta);
        }
        int lo = -2, hi = q-1;
        while(lo < hi) {
            int m = (lo+hi+5)/2-2;
            auto node = seg.get(m, q-1);
            if(node.mx-node.mn < c[i]) {
                hi = m-1;
            }
            else {
                lo = m;
            }
        }
        auto node = seg.get(lo, q-1);
        if(node.mni < node.mxi) {
            // increased, hit max capacity, decreased without going lower than 0
            s[i] = c[i]-(node.mx-seg.get(q-1, q-1).mx);
        }
        else {
            // decreased, hit 0, increased without going above capacity
            s[i] = seg.get(q-1, q-1).mx-node.mn;
        }
    }
    return s;
}

//namespace Tests {
//    void test_segment_tree() {
//        Seg s;
//        vector<int> arr = {2, 4, 1, 1, -2, 5, 2};
//        q = arr.size();
//        s.build();
//        for(int i = 0; i < (int)arr.size(); i++) {
//            s.range_add(i, i, arr[i]);
//        }
//        for(int i = 0; i < 10; i++) {
//            int a = rand() % q, b = rand() % q;
//            if(a > b) swap(a, b);
//            ll delta = rand()%11-5;
//            s.range_add(a, b, delta);
//            for(int j = a; j <= b; j++) arr[j] += delta;
//        }
//        vector<pair<int, int>> ranges;
//        for(int i = 0; i < 10; i++) {
//            int a = rand() % q, b = rand() % q;
//            if(a > b) swap(a, b);
//            ranges.push_back({a, b});
//        }
//        for(auto p : ranges) {
//            Node res = s.get(p.first, p.second);
//            printf("(%d, %d) max: %lld (%d), min: %lld (%d)\n", p.first, p.second,
//                   res.mx, res.mxi, res.mn, res.mni);
//            auto it_max = max_element(arr.begin()+p.first, arr.begin()+p.second+1);
//            auto it_min = min_element(arr.begin()+p.first, arr.begin()+p.second+1);
//            assert(res.mx == *it_max);
//            assert(res.mn == *it_min);
//            assert(res.mxi == distance(arr.begin(), it_max));
//            assert(res.mni == distance(arr.begin(), it_min));
//        }
//        for(int i = 0; i < (int)arr.size(); i++) {
//            Node res = s.get(i, i);
//            printf("i = %d:\nmax: %lld (%d), min: %lld (%d)\n", i, res.mx, res.mxi, res.mn, res.mni);
//        }
//    }
//}

컴파일 시 표준 에러 (stderr) 메시지

candies.cpp:10:2: warning: #warning change mxn back [-Wcpp]
   10 | #warning change mxn back
      |  ^~~~~~~

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