| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 1065502 |
2024-08-19T08:37:54 Z |
정민찬(#11118) |
Food Court (JOI21_foodcourt) |
C++17 |
|
91 ms |
53696 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll,ll> pll;
struct SegmentTree{
vector<ll> tree;
void init(ll n) {
ll sz = 1 << __lg(n-1) + 2;
tree.assign(sz, 0);
}
void update(ll node, ll s, ll e, ll tar, ll val) {
if (s > tar || tar > e) return;
tree[node] += val;
if (s == e) {
return;
}
ll mid = s + e >> 1;
update(node*2, s, mid, tar, val);
update(node*2+1, mid+1, e, tar, val);
tree[node] = tree[node*2] + tree[node*2+1];
}
ll query(ll node, ll s, ll e, ll l, ll r) {
if (l > e || s > r) return 0;
if (l <= s && e <= r) return tree[node];
ll mid = s + e >> 1;
return query(node*2, s, mid, l, r) + query(node*2+1, mid+1, e, l, r);
}
pll findLeft(ll node, ll s, ll e, ll l, ll r, ll k) {
if (l > e || s > r) return {-1, 0};
if (tree[node] < k) return {-1, tree[node]};
if (s == e) return {s, 0};
ll mid = s + e >> 1;
pll t = findLeft(node*2, s, mid, l, r, k);
if (t.first == -1) {
pll t2 = findLeft(node*2+1, mid+1, e, l, r, k - t.second);
return {t2.first, t.second + t2.second};
}
return t;
}
};
struct Node{
ll sum, mnl, mnidx;
};
Node Merge(Node u, Node v) {
Node ret;
ret.sum = u.sum + v.sum;
if (u.mnl <= u.sum + v.mnl) {
ret.mnl = u.mnl;
ret.mnidx = u.mnidx;
}
else {
ret.mnl = u.sum + v.mnl;
ret.mnidx = v.mnidx;
}
return ret;
}
struct SegmentTree2{
vector<Node> tree;
void init(ll n) {
ll sz = 1 << __lg(n-1) + 2;
tree.resize(sz);
build(1, 1, n);
}
void build(ll node, ll s, ll e) {
if (s == e) {
tree[node] = {0, 0, s-1};
return;
}
ll mid = s + e >> 1;
build(node*2, s, mid);
build(node*2+1, mid+1, e);
tree[node] = Merge(tree[node*2], tree[node*2+1]);
}
void update(ll node, ll s, ll e, ll tar, ll val) {
if (s > tar || tar > e) return;
if (s == e) {
if (val < 0) tree[node] = {val, val, s};
else tree[node] = {val, 0, s-1};
return;
}
ll mid = s + e >> 1;
update(node*2, s, mid, tar, val);
update(node*2+1, mid+1, e, tar, val);
tree[node] = Merge(tree[node*2], tree[node*2+1]);
}
Node query(ll node, ll s, ll e, ll l, ll r) {
if (l <= s && e <= r) return tree[node];
ll mid = s + e >> 1;
if (r <= mid) return query(node*2, s, mid, l, r);
if (l >= mid+1) return query(node*2+1, mid+1, e, l, r);
return Merge(query(node*2, s, mid, l, r), query(node*2+1, mid+1, e, l, r));
}
};
vector<array<ll,3>> upd[250010];
vector<pll> qry[250010];
SegmentTree pseg, mseg;
SegmentTree2 seg2;
int main() {
ios_base :: sync_with_stdio(false); cin.tie(NULL);
ll N, M, Q;
cin >> N >> M >> Q;
vector<ll> num(Q + 1, -1);
for (ll i=1; i<=Q; i++) {
ll t;
cin >> t;
if (t == 1) {
ll l, r, c, k;
cin >> l >> r >> c >> k;
upd[l].push_back({i, k, c});
upd[r+1].push_back({i, -k, c});
num[i] = c;
}
else if (t == 2) {
ll l, r, k;
cin >> l >> r >> k;
upd[l].push_back({i, k, 0});
upd[r+1].push_back({i, -k, 0});
}
else {
ll a, b;
cin >> a >> b;
qry[a].push_back({i, b});
}
}
pseg.init(Q);
mseg.init(Q);
seg2.init(Q);
vector<ll> ans(Q+1, -1);
for (ll i=1; i<=M; i++) {
for (auto &[j, k, c] : upd[i]) {
if (c != 0) {
pseg.update(1, 1, Q, j, k);
if (k < 0) seg2.update(1, 1, Q, j, 0);
else seg2.update(1, 1, Q, j, k);
}
else {
mseg.update(1, 1, Q, j, k);
if (k < 0) seg2.update(1, 1, Q, j, 0);
else seg2.update(1, 1, Q, j, -k);
}
}
for (auto &[j, cnt] : qry[i]) {
Node ret = seg2.query(1, 1, Q, 1, j);
ll mret = mseg.query(1, 1, Q, ret.mnidx + 1, j);
if (pseg.query(1, 1, Q, ret.mnidx+1, j) < mret + cnt) {
ans[j] = 0;
continue;
}
ll pret = pseg.findLeft(1, 1, Q, ret.mnidx+1, j, mret + cnt).first;
ans[j] = num[pret];
}
}
for (ll i=1; i<=Q; i++) {
if (ans[i] != -1) {
cout << ans[i] << '\n';
}
}
}
Compilation message
foodcourt.cpp: In member function 'void SegmentTree::init(ll)':
foodcourt.cpp:11:32: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
11 | ll sz = 1 << __lg(n-1) + 2;
| ~~~~~~~~~~^~~
foodcourt.cpp: In member function 'void SegmentTree::update(ll, ll, ll, ll, ll)':
foodcourt.cpp:20:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
20 | ll mid = s + e >> 1;
| ~~^~~
foodcourt.cpp: In member function 'll SegmentTree::query(ll, ll, ll, ll, ll)':
foodcourt.cpp:28:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
28 | ll mid = s + e >> 1;
| ~~^~~
foodcourt.cpp: In member function 'pll SegmentTree::findLeft(ll, ll, ll, ll, ll, ll)':
foodcourt.cpp:35:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
35 | ll mid = s + e >> 1;
| ~~^~~
foodcourt.cpp: In member function 'void SegmentTree2::init(ll)':
foodcourt.cpp:66:32: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
66 | ll sz = 1 << __lg(n-1) + 2;
| ~~~~~~~~~~^~~
foodcourt.cpp: In member function 'void SegmentTree2::build(ll, ll, ll)':
foodcourt.cpp:75:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
75 | ll mid = s + e >> 1;
| ~~^~~
foodcourt.cpp: In member function 'void SegmentTree2::update(ll, ll, ll, ll, ll)':
foodcourt.cpp:87:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
87 | ll mid = s + e >> 1;
| ~~^~~
foodcourt.cpp: In member function 'Node SegmentTree2::query(ll, ll, ll, ll, ll)':
foodcourt.cpp:94:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
94 | ll mid = s + e >> 1;
| ~~^~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
12376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
12376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
57 ms |
22864 KB |
Output is correct |
| 2 |
Correct |
59 ms |
23256 KB |
Output is correct |
| 3 |
Correct |
62 ms |
22952 KB |
Output is correct |
| 4 |
Correct |
57 ms |
22868 KB |
Output is correct |
| 5 |
Incorrect |
58 ms |
23256 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
91 ms |
53696 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
12376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
59 ms |
22364 KB |
Output is correct |
| 2 |
Correct |
61 ms |
22940 KB |
Output is correct |
| 3 |
Correct |
64 ms |
23124 KB |
Output is correct |
| 4 |
Correct |
44 ms |
21328 KB |
Output is correct |
| 5 |
Correct |
63 ms |
22216 KB |
Output is correct |
| 6 |
Correct |
61 ms |
23128 KB |
Output is correct |
| 7 |
Correct |
40 ms |
21296 KB |
Output is correct |
| 8 |
Correct |
34 ms |
21128 KB |
Output is correct |
| 9 |
Correct |
52 ms |
22344 KB |
Output is correct |
| 10 |
Correct |
39 ms |
21596 KB |
Output is correct |
| 11 |
Correct |
58 ms |
22964 KB |
Output is correct |
| 12 |
Correct |
55 ms |
23120 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
12376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
4 ms |
12376 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
