#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
typedef long long ll;
const ll maxn = 250010;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
struct Treap
{
struct Node
{
ll pr, key, sz, key_sum, gr;
Node *l, *r;
Node(ll _key, ll _gr)
{
gr = _gr;
sz = 1;
pr = rand();
key = _key;
key_sum = _key;
l = r = NULL;
}
void prll()
{
if (l) l -> prll();
cout << key << " ";
if (r) r -> prll();
}
void con()
{
sz = 1;
key_sum = key;
if (l)
{
sz += l -> sz;
key_sum += l -> key_sum;
}
if (r)
{
sz += r -> sz;
key_sum += r -> key_sum;
}
}
};
Node *root = NULL;
void SplitSum(Node *T, Node *&L, Node *&R, ll qsum)
{
if (T == NULL)
{
L = R = NULL;
return;
}
ll sum = T -> key;
if (T -> l)
sum += T -> l -> key_sum;
if (qsum >= sum)
{
L = T;
SplitSum(T -> r, L -> r, R, qsum - sum);
}
else
{
R = T;
SplitSum(T -> l, L, R -> l, qsum);
}
T -> con();
}
void SplitSize(Node *T, Node *&L, Node *&R, ll qsize)
{
///cout << "again" << endl;
if (T == NULL)
{
L = R = NULL;
return;
}
ll _sz = 1;
if (T -> l)
_sz += T -> l -> sz;
///cout << T -> key << " " << _sz << endl;
if (qsize >= _sz)
{
L = T;
SplitSize(T -> r, L -> r, R, qsize - _sz);
}
else
{
///cout << "hey" << endl;
R = T;
SplitSize(T -> l, L, R -> l, qsize);
}
T -> con();
}
void Merge(Node *&T, Node *L, Node *R)
{
if (L == NULL && R == NULL)
{
T = NULL;
return;
}
if (L == NULL)
{
T = R;
return;
}
if (R == NULL)
{
T = L;
return;
}
if (L -> pr > R -> pr)
{
T = L;
Merge(T -> r, L -> r, R);
}
else
{
T = R;
Merge(T -> l, L, R -> l);
}
T -> con();
}
void Insert(ll _key, ll _gr)
{
///cout << "Insert" << endl;
Node *M = new Node(_key, _gr);
Merge(root, root, M);
}
void Erase(ll k)
{
if (root == NULL)
return;
if (root -> key_sum < k)
{
root = NULL;
return;
}
Node *L, *M, *R;
SplitSum(root, L, R, k);
if (L != NULL)
k -= L -> key_sum;
if (k != 0)
{
SplitSize(R, M, R, 1);
M -> key -= k;
M -> key_sum -= k;
Merge(R, M, R);
}
root = R;
}
ll query(ll pos)
{
if (root == NULL)
return 0;
if (root -> key_sum < pos)
return 0;
///cout << root -> key_sum << endl;
Node *L, *M, *R;
SplitSum(root, L, R, pos - 1);
SplitSize(R, M, R, 1);
ll ans = M -> gr;
Merge(R, M, R);
Merge(root, L, R);
return ans;
}
};
ll n, m, q;
Treap tree[4 * maxn];
vector < pair < ll, ll > >lazy_add[4 * maxn], lazy_rem[4 * maxn];
void push_lazy(ll root, ll left, ll right)
{
if (left != right)
{
for (ll j = 0; j < lazy_add[root].size(); j ++)
{
lazy_add[root * 2].push_back(lazy_add[root][j]);
lazy_add[root * 2 + 1].push_back(lazy_add[root][j]);
}
for (ll j = 0; j < lazy_rem[root].size(); j ++)
{
lazy_rem[root * 2].push_back(lazy_rem[root][j]);
lazy_rem[root * 2 + 1].push_back(lazy_rem[root][j]);
}
}
if (left == right)
{
for (ll j = 0; j < lazy_add[root].size(); j ++)
{
tree[root].Insert(lazy_add[root][j].first, lazy_add[root][j].second);
}
for (ll j = 0; j < lazy_rem[root].size(); j ++)
{
///cout << "here" << endl;
///cout << left << " " << right << endl;
tree[root].Erase(lazy_rem[root][j].first);
}
}
lazy_add[root].clear();
lazy_rem[root].clear();
///if (tree[root].root != NULL)
/// cout << left << " - " << right << " " << tree[root].root -> key_sum << endl;
}
void update_range(ll root, ll left, ll right,
ll qleft, ll qright, ll c, ll k, ll t)
{
push_lazy(root, left, right);
if (left > qright || right < qleft)
return;
///cout << root << " - " << left << " " << right << " " << qleft << " " << qright << " " <<c << " " << k << endl;
if (left >= qleft && right <= qright)
{
///cout << "here" << endl;
if (t == 1)
lazy_add[root].push_back({k, c});
else
lazy_rem[root].push_back({k, c});
push_lazy(root, left, right);
return;
}
ll mid = (left + right) / 2;
update_range(root * 2, left, mid, qleft, qright, c, k, t);
update_range(root * 2 + 1, mid + 1, right, qleft, qright, c, k, t);
}
ll poll_query(ll root, ll left, ll right, ll idx, ll k)
{
push_lazy(root, left, right);
if (left == right)
return tree[root].query(k);
ll mid = (left + right) / 2;
if (idx <= mid)
{
return poll_query(root * 2, left, mid, idx, k);
}
else
{
return poll_query(root * 2 + 1, mid + 1, right, idx, k);
}
}
void solve()
{
cin >> n >> m >> q;
for (ll i = 1; i <= q; i ++)
{
ll type;
cin >> type;
if (type == 1)
{
ll l, r, c, k;
cin >> l >> r >> c >> k;
update_range(1, 1, n, l, r, c, k, 1);
}
else
if (type == 2)
{
ll l, r, k;
cin >> l >> r >> k;
update_range(1, 1, n, l, r, 0, k, 2);
}
else
{
ll a, b;
cin >> a >> b;
ll ans = poll_query(1, 1, n, a, b);
cout << ans << endl;;
}
}
}
int main()
{
speed();
solve();
return 0;
}
Compilation message
foodcourt.cpp: In function 'void push_lazy(ll, ll, ll)':
foodcourt.cpp:206:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
206 | for (ll j = 0; j < lazy_add[root].size(); j ++)
| ~~^~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:211:26: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
211 | for (ll j = 0; j < lazy_rem[root].size(); j ++)
| ~~^~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:219:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
219 | for (ll j = 0; j < lazy_add[root].size(); j ++)
| ~~^~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:224:22: warning: comparison of integer expressions of different signedness: 'll' {aka 'long long int'} and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
224 | for (ll j = 0; j < lazy_rem[root].size(); j ++)
| ~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
66360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
66360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
330 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
500 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
66360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
436 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
66360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
52 ms |
66360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
