oj.uz

Submission #882273

# Submission time Handle Problem Language Result Execution time Memory
882273 2023-12-02T21:27:59 Z Regulus Food Court (JOI21_foodcourt) C++17
13 / 100
 46 ms 19028 KB 
#include <bits/stdc++.h>            // pA
#define IO ios::sync_with_stdio(false);cin.tie(0);
#define debug(x) cerr << #x << " = " << (x) << ' '
#define endl cerr << '\n'
#define all(v) (v).begin(), (v).end()
#define SZ(v) (ll)(v).size()
#define lowbit(x) (x)&-(x)
#define pb emplace_back
#define F first
#define S second
using namespace std;
using ll = long long;
using pll = pair<ll, ll>;

const int N = 3e5+5;
//const int INF = 2e9;
ll Q, bit[N], a[N], ans[N];
struct Query {
    ll t, tin, c, k;
    Query() {}
    Query(ll tt, ll tttt, ll cc, ll kk) : t(tt), tin(tttt), c(cc), k(kk) {}
};
vector<Query> v[N];
vector<int> v2;

inline ll query(int x)
{
    ll ret = 0;
    for (int i=x; i > 0; i-=lowbit(i)) ret += bit[i];
    return ret;
}

inline void upd(ll x, ll val)
{
    for (int i=x; i <= Q; i+=lowbit(i)) bit[i] += val;
}

inline bool cmp(Query a, Query b) { return a.tin < b.tin; }

int main(void)
{ IO
    ll n, m, i, t, L, R, c, k, lb, ub, mid;

    cin >> n >> m >> Q;
    for (i=1; i <= Q; ++i)
    {
        cin >> t;
        if (t == 1)
        {
            cin >> L >> R >> c >> k;
            v[L].pb(t, i, c, k);
            v[R+1].pb(-t, i, c, k);
        } else if (t == 2) {
            assert(0);
        } else if (t == 3) {
            cin >> L >> k;
            v[L].pb(t, i, 0, k), v2.pb(i);
        } else while (1);
    }

    for (i=1; i <= n; ++i)
    {
        sort(all(v[i]), cmp);
        for (auto q : v[i])
        {
            if (q.t == 1) upd(q.tin, q.k), a[q.tin] = q.c;
            else if (q.t == -1) upd(q.tin, -q.k), a[q.tin] = 0;
            else {
                lb = 1, ub = q.tin;
                while (lb < ub)
                {
                    mid = (lb+ub)>>1;
                    if (query(mid) >= q.k) ub = mid;
                    else lb = mid + 1;
                }
                if (lb == q.tin) ans[q.tin] = 0;
                else if (a[lb] == 0) assert(0);
                else ans[q.tin] = a[lb];
            }
        }
    }

    for (int x : v2) cout << ans[x] << '\n';

    return 0;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 17496 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 17496 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Runtime error 9 ms 17500 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 17552 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 17496 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 15284 KB Output is correct
2 Correct 39 ms 19024 KB Output is correct
3 Correct 39 ms 17488 KB Output is correct
4 Correct 36 ms 17244 KB Output is correct
5 Correct 33 ms 18268 KB Output is correct
6 Correct 46 ms 19028 KB Output is correct
7 Correct 29 ms 17860 KB Output is correct
8 Correct 27 ms 15280 KB Output is correct
9 Correct 36 ms 18352 KB Output is correct
10 Correct 26 ms 17496 KB Output is correct
11 Correct 39 ms 18784 KB Output is correct
12 Correct 43 ms 19028 KB Output is correct

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 17496 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #8
0 / 11.0

# Verdict Execution time Memory Grader output
1 Runtime error 8 ms 17496 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -