oj.uz

답안 #797253

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
797253 2023-07-29T08:34:25 Z vjudge1 푸드 코트 (JOI21_foodcourt) C++17
0 / 100
 1000 ms 524288 KB 
#ifdef Home
#define _GLIBCXX_DEBUG
#endif // Home

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef deque < pair < ll, int > > QQ;

map < int, QQ > ShopsL, ShopsR;

void del(int i, int K) {
    if(ShopsL[i].empty() || ShopsL[i].back().first < K) {
        if(!ShopsL[i].empty()) {
            K -= ShopsL[i].back().first;
        }
        for(; !ShopsL[i].empty(); ShopsL[i].pop_back());
        for(int cnt; !ShopsR[i].empty();) {
            cnt = ShopsR[i].back().first - (ShopsR[i].size() == 1 ? 0ll : ShopsR[i][ShopsR[i].size() - 2].first);
            ShopsL[i].push_back({(ShopsL[i].empty() ? 0ll : ShopsL[i].back().first) + cnt, ShopsR[i].back().second});
            ShopsR[i].pop_back();
        }
    }
    for(int cnt; K && !ShopsL[i].empty();) {
        cnt = ShopsL[i].back().first - (ShopsL[i].size() == 1 ? 0ll : ShopsL[i][ShopsL[i].size() - 2].first);
        if(K < cnt) {
            ShopsL[i].back().first -= K;
            K = 0;
        } else {
            K -= cnt;
            ShopsL[i].pop_back();
        }
    }
}

void add(int i, ll K, int C) {
    if(!C) {
        del(i, K);
        return;
    }
    ShopsR[i].push_back({K + (ShopsR[i].empty() ? 0ll : ShopsR[i].back().first), C});
}

int Get(int i, ll K) {
    if((ShopsL[i].empty() ? 0ll : ShopsL[i].back().first) + (ShopsR[i].empty() ? 0ll : ShopsR[i].back().first) < K) {
        return 0;
    }
    if(ShopsL[i].empty() || ShopsL[i].back().first < K) {
        if(!ShopsL[i].empty()) {
            K -= ShopsL[i].back().first;
        }
        int l = -1, r = ShopsR[i].size() - 1, m;
        for(; l + 1 < r;) {
            m = (l + r) / 2;
            (ShopsR[i][m].first < K ? l : r) = m;
        }
        return ShopsR[i].empty() ? 0ll : ShopsR[i][r].second;
    } 
    int l = 0, r = ShopsL[i].size(), m;
    for(; l + 1 < r;) {
        m = (l + r) / 2;
        (ShopsL[i][m].first < K ? r : l) = m;
    }
    return ShopsL[i].empty() ? 0ll : ShopsL[i][l].second;
}

struct node{
    node *left = NULL, *right = NULL;
    int l, r;
    queue < pair < ll, int > > q;
    node(int l, int r) :l(l),r(r){};
};

void relax(node *x, int i) {
    for(; !x->q.empty(); x->q.pop()) {
        add(i, x->q.front().first, x->q.front().second);
    }
}

void Push(pair < int, int > tmp, node *x) {
    if(x->q.empty() || x->q.back().second != tmp.second) {
        x->q.push(tmp);
        return;
    }
    x->q.back().first += tmp.first;
}

void push(node *x) {
    if(x->left == NULL) {
        x->left = new node(x->l, (x->r + x->l) / 2);
    }
    if(x->right == NULL) {
        x->right = new node((x->l + x->r) / 2, x->r);
    }
    for(; !x->q.empty(); x->q.pop()) {
        Push(x->q.front(), x->left);
        Push(x->q.front(), x->right);
    }
}

void add_to_que(int l, int r, pair < int, int > tmp, node *x) {
    if(r <= x->l || x->r <= l) {
        return;
    }
    if(l <= x->l && x->r <= r) {
        Push(tmp, x);
        return;
    }
    push(x);
    add_to_que(l, r, tmp, x->left);
    add_to_que(l, r, tmp, x->right);
}

int get(int pos, ll K, node *x) {
    if(x->l + 1 == x->r) {
        relax(x, x->l);
        return Get(x->l, K);
    }
    push(x);
    return pos < x->left->r ? 
    get(pos, K, x->left) :
    get(pos, K, x->right) ;
}

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);
    node *tree = new node(0, k);
    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, tree);
        } else if(t == 2) {
            cin >> L >> R >> K;
            ++ R;
            tmp = {K, 0};
            add_to_que(L, R, tmp, tree);
        } else {
            cin >> C >> T;
            cout << get(C, T, tree) << '\n';
        }
    }
}

Compilation message

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

Subtask #1
0 / 2.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

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

Subtask #4
0 / 21.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1006 ms 524288 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

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

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 910 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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