#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define mp make_pair
#define pb push_back
#define ii pair<int, int>
#define pl pair<ll, ll>
#define f1 first
#define s2 second
const int MAX = 250069;
const ll inf = 1e18 + 69;
struct Segtree1
{
int n;
ll st[1 << 19], lz1[1 << 19], lz2[1 << 19];
Segtree1(int _n) : n(_n) {}
inline void propagate(int node, int l, int r)
{
st[node] = max(st[node] + lz1[node], lz2[node]);
if (l < r)
{
lz1[node << 1] += lz1[node];
lz2[node << 1] += lz1[node];
lz2[node << 1] = max(lz2[node << 1], lz2[node]);
lz1[node << 1 | 1] += lz1[node];
lz2[node << 1 | 1] += lz1[node];
lz2[node << 1 | 1] = max(lz2[node << 1 | 1], lz2[node]);
}
lz1[node] = lz2[node] = 0;
}
inline void add(int p, int q, ll val)
{
const auto add_ = [&](const auto &self, int node, int l, int r) -> void
{
propagate(node, l, r);
if (l > q || r < p)
return;
if (p <= l && r <= q)
{
lz1[node] += val; lz2[node] += val;
propagate(node, l, r);
return;
}
int mid = (l + r) >> 1;
self(self, node << 1, l, mid);
self(self, node << 1 | 1, mid+1, r);
st[node] = max(st[node << 1], st[node << 1 | 1]);
};
add_(add_, 1, 1, n);
}
// Ai = max(Ai, val) for i in [p <= i <= q]
inline void update(int p, int q, ll val)
{
const auto update_ = [&](const auto &self, int node, int l, int r) -> void
{
propagate(node, l, r);
if (l > q || r < p)
return;
if (p <= l && r <= q)
{
lz2[node] = max(lz2[node], (ll)val);
propagate(node, l, r);
return;
}
int mid = (l + r) >> 1;
self(self, node << 1, l, mid);
self(self, node << 1 | 1, mid+1, r);
st[node] = max(st[node << 1], st[node << 1 | 1]);
};
update_(update_, 1, 1, n);
}
inline ll query(ll p)
{
const auto query_ = [&](const auto &self, int node, int l, int r) -> ll
{
propagate(node, l, r);
if (l > p || r < p)
return -1;
if (p <= l && r <= p)
return st[node];
int mid = (l + r) >> 1;
return max(self(self, node << 1, l, mid), self(self, node << 1 | 1, mid+1, r));
};
return query_(query_, 1, 1, n);
}
};
struct Segtree2
{
int n;
ll st[1 << 19], lz[1 << 19];
Segtree2 (int _n) : n(_n) {}
inline void propagate(int node, int l, int r)
{
st[node] += lz[node];
if (l < r)
{
lz[node << 1] += lz[node];
lz[node << 1 | 1] += lz[node];
}
lz[node] = 0;
}
inline void add(int p, int q, ll val)
{
const auto add_ = [&](const auto &self, int node, int l, int r) -> void
{
propagate(node, l, r);
if (l > q || r < p)
return;
if (p <= l && r <= q)
{
lz[node] += val;
propagate(node, l, r);
return;
}
int mid = (l + r) >> 1;
self(self, node << 1, l, mid);
self(self, node << 1 | 1, mid+1, r);
st[node] = min(st[node << 1], st[node << 1 | 1]);
};
add_(add_, 1, 0, n-1);
}
inline void modify(int p, ll val)
{
const auto modify_ = [&](const auto &self, int node, int l, int r) -> void
{
propagate(node, l, r);
if (l > p || r < p)
return;
if (p <= l && r <= p)
{
st[node] = val;
return;
}
int mid = (l + r) >> 1;
self(self, node << 1, l, mid);
self(self, node << 1 | 1, mid+1, r);
st[node] = min(st[node << 1], st[node << 1 | 1]);
};
modify_(modify_, 1, 0, n-1);
}
inline int query()
{
const auto query_ = [&](const auto &self, int node, int l, int r) -> int
{
propagate(node, l, r);
if (l == r)
return l;
int mid = (l + r) >> 1;
propagate(node << 1, l, mid);
if (st[node << 1] < 0)
return self(self, node << 1, l, mid);
return self(self, node << 1 | 1, mid+1, r);
};
return query_(query_, 1, 0, n-1);
}
};
int main()
{
ios :: sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int N, M, Q;
cin >> N >> M >> Q;
int ty[MAX], L[MAX], R[MAX];
ll A[MAX], B[MAX];
for (int i = 0; i < Q; ++i)
{
cin >> ty[i];
if (ty[i] == 1) cin >> L[i] >> R[i] >> B[i] >> A[i];
else if (ty[i] == 2) cin >> L[i] >> R[i] >> A[i];
else cin >> A[i] >> B[i];
}
int askQ = 0;
ll ans[MAX];
vector<pair<pl, int>> query;
Segtree1 st1(N);
for (int i = 0; i < Q; ++i)
{
if (ty[i] == 1)
{
st1.add(L[i], R[i], A[i]);
}
else if (ty[i] == 2)
{
st1.add(L[i], R[i], -A[i]);
st1.update(L[i], R[i], 0);
}
else
{
if (st1.query(A[i]) >= B[i]) cout << 1 << '\n';
else cout << 0 << '\n';
// if (st1.query(A[i]) >= B[i]) query.pb({{A[i], st1.query(A[i]) - B[i]}, askQ++});
// else ans[askQ++] = 0;
}
}
return 0;
sort(query.begin(), query.end());
cerr << "query: \n";
for (int i = 0; i < (int)query.size(); ++i)
cerr << query[i].f1.f1 << " " << query[i].f1.s2 << " " << query[i].s2 << '\n';
cerr << '\n';
Segtree2 st2(N);
for (int i = Q-1, j = (int)query.size()-1; i >= 0; --i)
{
if (ty[i] <= 2)
{
int l = (int)(lower_bound(query.begin(), query.end(), mp(mp((ll)L[i], 0ll), 0)) - query.begin());
int r = -1 + (int)(upper_bound(query.begin(), query.end(), mp(mp((ll)R[i], inf), 0)) - query.begin());
cerr << L[i] << " " << R[i] << " " << l << " " << r << '\n';
if (l <= r)
{
if (ty[i] == 1) st2.add(l, r, -A[i]);
else st2.add(l, r, A[i]);
}
while (st2.st[1] < 0)
{
cerr << "i: " << i << '\n';
int id = st2.query();
ans[query[id].s2] = B[i];
st2.modify(id, inf);
}
}
else
{
int id = (int)(lower_bound(query.begin(), query.end(), mp(mp(A[i], B[i]), j--)) - query.begin());
st2.modify(id, B[i]);
}
}
for (int i = 0; i < askQ; ++i)
cout << ans[i] << '\n';
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
19496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
19496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
107 ms |
20664 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
456 ms |
25088 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
19496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
73 ms |
20912 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
19496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
10 ms |
19496 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
