#include <bits/stdc++.h>
#define endl '\n'
using namespace std;
const int maxn = 250010;
typedef long long ll;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
}
struct Treap
{
struct Node
{
int pr, key, sz, key_sum, gr;
Node *l, *r;
Node(int _key, int _gr)
{
gr = _gr;
sz = 1;
pr = rand();
key = _key;
key_sum = _key;
l = r = NULL;
}
void print()
{
if (l) l -> print();
cout << key << " ";
if (r) r -> print();
}
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, int qsum)
{
if (T == NULL)
{
L = R = NULL;
return;
}
int 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, int qsize)
{
///cout << "again" << endl;
if (T == NULL)
{
L = R = NULL;
return;
}
int _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(int _key, int _gr)
{
///cout << "Insert" << endl;
Node *M = new Node(_key, _gr);
Merge(root, root, M);
}
void Erase(int 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;
}
int query(int 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);
int ans = M -> gr;
Merge(R, M, R);
Merge(root, L, R);
return ans;
}
};
int n, m, q;
Treap tree[4 * maxn];
vector < pair < int, int > >lazy_add[4 * maxn], lazy_rem[4 * maxn];
void push_lazy(int root, int left, int right)
{
if (left != right)
{
for (int 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 (int 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 (int j = 0; j < lazy_add[root].size(); j ++)
{
tree[root].Insert(lazy_add[root][j].first, lazy_add[root][j].second);
}
for (int 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(int root, int left, int right,
int qleft, int qright, int c, int k, int 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;
}
int 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);
}
int point_query(int root, int left, int right, int idx, int k)
{
push_lazy(root, left, right);
if (left == right)
return tree[root].query(k);
int mid = (left + right) / 2;
if (idx <= mid)
{
return point_query(root * 2, left, mid, idx, k);
}
else
{
return point_query(root * 2 + 1, mid + 1, right, idx, k);
}
}
void solve()
{
cin >> n >> m >> q;
for (int i = 1; i <= q; i ++)
{
int type;
cin >> type;
if (type == 1)
{
int l, r, c, k;
cin >> l >> r >> c >> k;
update_range(1, 1, n, l, r, c, k, 1);
}
else
if (type == 2)
{
int l, r, k;
cin >> l >> r >> k;
update_range(1, 1, n, l, r, 0, k, 2);
}
else
{
int a, b;
cin >> a >> b;
int ans = point_query(1, 1, n, a, b);
cout << ans << endl;;
}
}
}
int main()
{
speed();
solve();
return 0;
}
Compilation message
foodcourt.cpp: In function 'void push_lazy(int, int, int)':
foodcourt.cpp:205:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
205 | for (int j = 0; j < lazy_add[root].size(); j ++)
| ~~^~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:210:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
210 | for (int j = 0; j < lazy_rem[root].size(); j ++)
| ~~^~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:218:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
218 | for (int j = 0; j < lazy_add[root].size(); j ++)
| ~~^~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:223:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
223 | for (int j = 0; j < lazy_rem[root].size(); j ++)
| ~~^~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
59204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
59204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
555 ms |
524292 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
84 ms |
48060 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
59204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
37 ms |
47492 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
59204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
59204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
