| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 421994 |
2021-06-09T14:33:54 Z |
lyc |
Food Court (JOI21_foodcourt) |
C++14 |
|
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) {}
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
3056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
3056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1070 ms |
9296 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1086 ms |
24108 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
3056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
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 |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
3056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
11 ms |
3056 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
