// #pragma GCC target("avx2")
// #pragma GCC optimize("O3")
// #include <x86intrin.h>
#include <bits/stdc++.h>
#include <chrono>
#include <random>
// @author: Vlapos
namespace operators
{
template <typename T1, typename T2>
std::istream &operator>>(std::istream &in, std::pair<T1, T2> &x)
{
in >> x.first >> x.second;
return in;
}
template <typename T1, typename T2>
std::ostream &operator<<(std::ostream &out, std::pair<T1, T2> x)
{
out << x.first << " " << x.second;
return out;
}
template <typename T1>
std::istream &operator>>(std::istream &in, std::vector<T1> &x)
{
for (auto &i : x)
in >> i;
return in;
}
template <typename T1>
std::ostream &operator<<(std::ostream &out, std::vector<T1> &x)
{
for (auto &i : x)
out << i << " ";
return out;
}
template <typename T1>
std::ostream &operator<<(std::ostream &out, std::set<T1> &x)
{
for (auto &i : x)
out << i << " ";
return out;
}
}
// name spaces
using namespace std;
using namespace operators;
// end of name spaces
// defines
#define ll long long
#define ull unsigned long long
#define pb push_back
#define mp make_pair
#define pii pair<int, int>
#define pll pair<ll, ll>
#define f first
#define s second
#define uint unsigned int
#define all(vc) vc.begin(), vc.end()
// end of defines
// usefull stuff
void boost()
{
ios_base ::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
inline int getbit(int &x, int &bt) { return (x >> bt) & 1; }
const int dx4[4] = {-1, 0, 0, 1};
const int dy4[4] = {0, -1, 1, 0};
const int dx8[8] = {-1, -1, -1, 0, 0, 1, 1, 1};
const int dy8[8] = {-1, -0, 1, -1, 1, -1, 0, 1};
const ll INF = (1e17) + 500;
const int BIG = (1e9) * 2 + 100;
const int MAXN = (1e5) + 5;
const int MOD7 = (1e9) + 7;
const int MOD9 = (1e9) + 9;
const uint MODFFT = 998244353;
#define int ll
struct segTree
{
struct Node
{
int mx = 0, op = 0;
};
vector<Node> tree;
int sz = 0;
void init(int n)
{
sz = 1;
while (sz < n)
sz *= 2;
tree.resize(2 * sz);
}
void upd(int v, int val)
{
tree[v].op += val;
tree[v].mx += val;
}
void push(int v, int lv, int rv)
{
if (rv - lv == 1 or tree[v].op == 0)
return;
upd(v * 2 + 1, tree[v].op);
upd(v * 2 + 2, tree[v].op);
tree[v].op = 0;
}
void updSeg(int l, int r, int val, int v, int lv, int rv)
{
push(v, lv, rv);
if (l <= lv and rv <= r)
{
upd(v, val);
return;
}
if (rv <= l or r <= lv)
return;
int m = (lv + rv) >> 1;
updSeg(l, r, val, v * 2 + 1, lv, m);
updSeg(l, r, val, v * 2 + 2, m, rv);
tree[v].mx = max(tree[v * 2 + 1].mx, tree[v * 2 + 2].mx);
}
void updSeg(int l, int r, int val)
{
updSeg(l, r, val, 0, 0, sz);
}
int getPos(int pos, int v, int lv, int rv)
{
push(v, lv, rv);
if (rv - lv == 1)
return tree[v].mx;
int m = (lv + rv) >> 1;
if (pos < m)
return getPos(pos, v * 2 + 1, lv, m);
return getPos(pos, v * 2 + 2, m, rv);
}
int getPos(int pos)
{
return getPos(pos, 0, 0, sz);
}
int getGoodPos(int v, int lv, int rv)
{
push(v, lv, rv);
if (rv - lv == 1)
return lv;
int m = (lv + rv) >> 1;
if (tree[v * 2 + 1].mx >= 0)
return getGoodPos(v * 2 + 1, lv, m);
return getGoodPos(v * 2 + 2, m, rv);
}
int getGoodPos()
{
return getGoodPos(0, 0, sz);
}
};
struct segTreeBF
{
struct Node
{
int add = 0, del = 0;
};
vector<Node> tree;
int sz = 0;
void init(int n)
{
sz = 1;
while (sz < n)
sz *= 2;
tree.resize(2 * sz);
}
void upd(int v, int val)
{
if (tree[v].add + val >= 0)
tree[v].add = tree[v].add + val;
else
{
tree[v].del += tree[v].add + val;
tree[v].add = 0;
}
}
void push(int v, int lv, int rv)
{
if (rv - lv == 1 or (tree[v].add == 0 and tree[v].del == 0))
return;
upd(v * 2 + 1, tree[v].del);
upd(v * 2 + 1, tree[v].add);
upd(v * 2 + 2, tree[v].del);
upd(v * 2 + 2, tree[v].add);
tree[v].add = tree[v].del = 0;
}
void updSeg(int l, int r, int val, int v, int lv, int rv)
{
push(v, lv, rv);
if (l <= lv and rv <= r)
{
upd(v, val);
return;
}
if (rv <= l or r <= lv)
return;
int m = (lv + rv) >> 1;
updSeg(l, r, val, v * 2 + 1, lv, m);
updSeg(l, r, val, v * 2 + 2, m, rv);
}
void updSeg(int l, int r, int val)
{
updSeg(l, r, val, 0, 0, sz);
}
int getPos(int pos, int v, int lv, int rv)
{
push(v, lv, rv);
if (rv - lv == 1)
{
return tree[v].add;
}
int m = (lv + rv) >> 1;
if (pos < m)
return getPos(pos, v * 2 + 1, lv, m);
return getPos(pos, v * 2 + 2, m, rv);
}
int getPos(int pos)
{
return getPos(pos, 0, 0, sz);
}
};
struct test
{
void solve(int testcase)
{
boost();
int n, m, q;
cin >> n >> m >> q;
int cntA = 0;
vector<vector<pair<pii, int>>> ops(n);
vector<pair<pii, pii>> updates;
segTreeBF bf1, bf2;
vector<int> ans;
bf1.init(n);
bf2.init(n);
for (int i = 0; i < q; ++i)
{
int tp;
cin >> tp;
if (tp == 1)
{
int l, r, c, k;
cin >> l >> r >> c >> k;
--l;
updates.pb({{l, r}, {c, k}});
bf1.updSeg(l, r, k);
bf2.updSeg(l, r, k);
}
else if (tp == 2)
{
int l, r, k;
cin >> l >> r >> k;
--l;
bf2.updSeg(l, r, -k);
}
else
{
int p, val;
cin >> p >> val;
--p;
int cntLeave = bf1.getPos(p) - bf2.getPos(p);
ans.pb(0);
if (bf2.getPos(p) >= val)
ops[p].pb({{cntLeave, val}, cntA});
cntA++;
}
}
for (int i = 0; i < n; ++i)
ops[i].pb({{INF, INF}, BIG});
segTree res;
res.init(n + 1);
for (int i = 0; i < n; ++i)
{
reverse(all(ops[i]));
pii val = ops[i].back().f;
res.updSeg(i, i + 1, -val.s - val.f);
}
for (auto [seg, vals] : updates)
{
res.updSeg(seg.f, seg.s, vals.s);
int p = res.getGoodPos();
while (p < n)
{
ans[ops[p].back().s] = vals.f;
ops[p].pop_back();
pii val = ops[p].back().f;
res.updSeg(p, p + 1, -val.s - val.f - res.getPos(p));
p = res.getGoodPos();
}
}
for (auto el : ans)
cout << el << '\n';
}
};
main()
{
boost();
int q = 1;
// cin >> q;
for (int i = 0; i < q; i++)
{
test t;
t.solve(i);
}
return 0;
}
//[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]//
// //
// Coded by Der_Vlἀpos //
// //
//[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[[]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]]//
Compilation message
foodcourt.cpp:336:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
336 | main()
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
66 ms |
11020 KB |
Output is correct |
| 2 |
Correct |
71 ms |
11108 KB |
Output is correct |
| 3 |
Incorrect |
68 ms |
11080 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
450 ms |
42132 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
97 ms |
11960 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
2 ms |
600 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
