oj.uz

Submission #882262

# Submission time Handle Problem Language Result Execution time Memory
882262 2023-12-02T21:08:24 Z Regulus Food Court (JOI21_foodcourt) C++17
0 / 100
 36 ms 17752 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];
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];

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 {
            cin >> L >> k;
            v[L].pb(t, i, 0, k);
        }
    }

    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) cout << "0\n";
                else if (a[lb] == 0) assert(0);
                else cout << a[lb] << '\n';
            }
        }
    }


    return 0;
}

Subtask #1
0 / 2.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 17752 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 10 ms 17752 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 8 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 17500 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 10 ms 17752 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 13472 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 10 ms 17752 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 10 ms 17752 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -