제출 #797094

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
797094		vjudge1	푸드 코트 (JOI21_foodcourt)	C++17	0 / 100	261 ms	524288 KiB

foodcourt

#ifdef Home
#define _GLIBCXX_DEBUG
#endif // Home

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;

struct SlideWindow{
    deque < pair < ll, int > > L, R, S;
    deque < int > cnt;

    SlideWindow() {
        L.push_back({0, 0});
        R.push_back({0, 0});
        cnt.push_back(0);
    }

    void del(int K) {
        if(L.back().first < K) {
            K -= L.back().first;
            for(; L.back().first; L.pop_back(), cnt.pop_back());
            for(; R.back().first;) {
                cnt.push_back(S.back().first);
                L.push_back({L.back().first + cnt.back(), S.back().second});
                S.pop_back();
                R.pop_back();
            }
        }
        for(; K && L.back().first;) {
            if(K < cnt.back()) {
                L.back().first -= K;
                cnt.back() -= K;
                K = 0;
            } else {
                K -= cnt.back();
                cnt.pop_back();
                L.pop_back();
            }
        }
    }

    void add(ll K, int C) {
        if(!C) {
            del(K);
            return;
        }
        R.push_back({K + R.back().first, C});
        S.push_back({K, C});
    }

    int get(ll K) {
        if(L.back().first + R.back().first < K) {
            return 0;
        }
        if(L.back().first < K) {
            K -= L.back().first;
            int l = 0, r = R.size(), m;
            for(; l + 1 < r;) {
                m = (l + r) / 2;
                (R[m].first < K ? l : r) = m;
            }
            return R[r].second;
        } 
        int l = 0, r = L.size(), m;
        for(; l + 1 < r;) {
            m = (l + r) / 2;
            (L[m].first < K ? r : l) = m;
        }
        return L[l].second;
    }
};

struct node{
    queue < pair < ll, int > > q;
};

const int N = 1<<18;

SlideWindow Shops[N];
node tree[N<<1];

void relax(int x, int i) {
    for(; !tree[x].q.empty(); tree[x].q.pop()) {
        Shops[i].add(tree[x].q.front().first, tree[x].q.front().second);
    }
}

void push(int x) {
    int l = x * 2 + 1, r = x * 2 + 2;
    for(; !tree[x].q.empty(); tree[x].q.pop()) {
        tree[l].q.push(tree[x].q.front());
        tree[r].q.push(tree[x].q.front());
    }
}

void add_to_que(int &l, int &r, pair < int, int > &tmp, int x, int lx, int rx) {
    if(r <= lx || rx <= l) {
        return;
    }
    if(l <= lx && rx <= r) {
        tree[x].q.push(tmp);
        return;
    }
    push(x);
    int m = (lx + rx) / 2;
    add_to_que(l, r, tmp, x * 2 + 1, lx, m);
    add_to_que(l, r, tmp, x * 2 + 2, m, rx);
}

int get(int &pos, ll &K, int x, int lx, int rx) {
    if(lx + 1 == rx) {
        relax(x, lx);
        return Shops[lx].get(K);
    }
    push(x);
    int m = (lx + rx) / 2;
    return pos < m ? 
    get(pos, K, x * 2 + 1, lx, m) :
    get(pos, K, x * 2 + 2, m, rx) ;
}

main() {
#ifdef Home
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif // Home
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    int n, m, q, k = 1;
    pair < int, int > tmp;
    ll T;
    for(cin >> n >> m >> q; k <= n; k <<= 1);
    for(int t, L, R, C, K; q --> 0;) {
        cin >> t;
        if(t == 1) {
            cin >> L >> R >> C >> K;
            tmp = {K, C};
            ++ R;
            add_to_que(L, R, tmp, 0, 0, k);
        } else if(t == 2) {
            cin >> L >> R >> K;
            ++ R;
            tmp = {K, 0};
            add_to_que(L, R, tmp, 0, 0, k);
        } else {
            cin >> C >> T;
            cout << get(C, T, 0, 0, k) << '\n';
        }
    }
}

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

foodcourt.cpp:126:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  126 | main() {
      | ^~~~

• Subtask 1: 0 / 2
• Subtask 2: 0 / 5
• Subtask 3: 0 / 7
• Subtask 4: 0 / 21
• Subtask 5: 0 / 15
• Subtask 6: 0 / 13
• Subtask 7: 0 / 26
• Subtask 8: 0 / 11