oj.uz

답안 #421994

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
421994 2021-06-09T14:33:54 Z lyc 푸드 코트 (JOI21_foodcourt) C++14
0 / 100
 1000 ms 77248 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] = new node(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 = 1, 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

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

Subtask #2
0 / 5.0

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

Subtask #3
0 / 7.0

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

Subtask #4
0 / 21.0

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

Subtask #5
0 / 15.0

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

Subtask #6
0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 331 ms 69268 KB Output is correct
2 Correct 365 ms 74180 KB Output is correct
3 Incorrect 381 ms 77248 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #7
0 / 26.0

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

Subtask #8
0 / 11.0

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