oj.uz

Submission #421999

# Submission time Handle Problem Language Result Execution time Memory
421999 2021-06-09T14:39:15 Z lyc Food Court (JOI21_foodcourt) C++14
13 / 100
 1000 ms 86800 KB 
#include <bits/stdc++.h>
using namespace std;

#define TRACE(x) cerr << #x << " :: " << x << endl
#define _ << " " <<
#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()
#define FOR(i,a,b) for(int i=(a);i<=(b);++i)
#define RFOR(i,a,b) for(int i=(a);i>=(b);--i)
typedef long long ll;

const int mxN = 250005;
const int mxM = 250005;
const int mxQ = 250005;

int N, M, Q;
int group[mxM];

int wtf = 0;

struct node {
    int s, e, m, id;
    ll v;
    node *l, *r;
    node(int s, int e): s(s), e(e), m((s+e)/2), v(0) {
        if (s != e) {
            l = new node(s,m);
            r = new node(m+1,e);
        }
    }

    node(node* n): s(n->s), e(n->e), m(n->m), v(n->v), l(n->l), r(n->r), id(++wtf) {}

    node* uadd(int a, int b, ll c) {
        node *n = new node(this);
        if (a <= s && e <= b) {
            n->v += c;
        } else {
            if (a <= m) n->l = l->uadd(a,b,c);
            if (b > m) n->r = r->uadd(a,b,c);
        }
        return n;
    }

    ll qsum(int a) {
        ll ret = v;
        if (s != e) {
            if (a <= m) ret += l->qsum(a);
            else ret += r->qsum(a);
        }
        return ret;
    }

    void debug() {
        TRACE(id _ s _ e _ v);
        if (s != e) {
            l->debug();
            r->debug();
        }
    }

} *enter[mxN];

ll leave[mxN];

int main() {
    ios::sync_with_stdio(0); cin.tie(0);

    cin >> N >> M >> Q;
    enter[0] = new node(1,N);
    memset(leave,0,sizeof leave);
    FOR(i,1,Q){
        int T, L, R, C, K, A;
        long long B;
        cin >> T;
        enter[i] = enter[i-1];
        if (T == 1) {
            cin >> L >> R >> C >> K;
            enter[i] = enter[i]->uadd(L,R,K);
            group[i] = C;
        } else if (T == 2) {
            cin >> L >> R >> K;
            FOR(a,L,R){
                ll cur = enter[i]->qsum(a);
                leave[a] += min(cur,(ll)K);
            }
        } else {
            cin >> A >> B;
            B += leave[A];

            int lo = 0, hi = i;
            while (hi-lo > 1) {
                int mid = (lo+hi)/2;
                if (enter[mid]->qsum(A) < B) lo = mid;
                else hi = mid;
            }

            if (hi == i) cout << 0 << '\n';
            else cout << group[hi] << '\n';
        }
    }
}

Compilation message

foodcourt.cpp: In constructor 'node::node(node*)':
foodcourt.cpp:24:15: warning: 'node::r' will be initialized after [-Wreorder]
   24 |     node *l, *r;
      |               ^
foodcourt.cpp:22:18: warning:   'int node::id' [-Wreorder]
   22 |     int s, e, m, id;
      |                  ^~
foodcourt.cpp:32:5: warning:   when initialized here [-Wreorder]
   32 |     node(node* n): s(n->s), e(n->e), m(n->m), v(n->v), l(n->l), r(n->r), id(++wtf) {}
      |     ^~~~

Subtask #1
0 / 2.0

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 9188 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 21.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1091 ms 23880 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

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

Subtask #6
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 391 ms 66256 KB Output is correct
2 Correct 470 ms 71044 KB Output is correct
3 Correct 444 ms 73792 KB Output is correct
4 Correct 271 ms 56136 KB Output is correct
5 Correct 391 ms 66760 KB Output is correct
6 Correct 448 ms 76796 KB Output is correct
7 Correct 54 ms 5336 KB Output is correct
8 Correct 39 ms 5828 KB Output is correct
9 Correct 92 ms 11788 KB Output is correct
10 Correct 206 ms 61292 KB Output is correct
11 Correct 303 ms 86800 KB Output is correct
12 Correct 289 ms 86472 KB Output is correct

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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