#include <bits/stdc++.h>
#define int long long
#define ll long long
#define pii pair<int, int>
#define pll pair<ll, ll>
#define F first
#define S second
using namespace std;
ll N, M, Q, seg[300005], lazy[300005], ans[300005], color[300005];
vector<pair<int, pair<int, pll>>> modifies, colors;
vector<pair<int, pll>> queries;
void modify(int mL, int mR, ll val, int i = 1, int L = 1, int R = Q + 1)
{
if (mL <= L && R <= mR)
lazy[i] += val;
else if (R < mL || mR < L)
return;
else
{
int mid = (L + R) / 2;
lazy[i * 2] += lazy[i];
lazy[i * 2 + 1] += lazy[i];
lazy[i] = 0;
modify(mL, mR, val, i * 2, L, mid);
modify(mL, mR, val, i * 2 + 1, mid + 1, R);
seg[i] = seg[i * 2 + 1] + lazy[i * 2 + 1];
}
}
int bsearch(ll val, int i = 1, int L = 1, int R = Q + 1)
{
if (L == R)
return L;
else
{
lazy[i * 2] += lazy[i];
lazy[i * 2 + 1] += lazy[i];
seg[i] += lazy[i];
lazy[i] = 0;
int mid = (L + R) / 2;
if (seg[i * 2] + lazy[i * 2] >= val)
return bsearch(val, i * 2, L, mid);
else
return bsearch(val, i * 2 + 1, mid + 1, R);
}
}
signed main()
{
ios::sync_with_stdio(0), cin.tie(0);
cin >> N >> M >> Q;
for (int i = 1; i <= Q; i++)
{
ll T, L, R, C, K;
cin >> T >> L >> R;
assert(T != 2);
if (T == 1)
{
cin >> C >> K;
modifies.emplace_back(pair<int, pair<int, pll>>{L, {i, {C, K}}});
modifies.emplace_back(pair<int, pair<int, pll>>{R + 1, {i, {-C, -K}}});
color[i] = C;
ans[i] = -1;
}
else
queries.emplace_back(pair<int, pll>{L, {i, R}});
}
sort(modifies.begin(), modifies.end());
sort(queries.begin(), queries.end());
int mdx = 0, qdx = 0;
for (int i = 1; i <= N; i++)
{
while (mdx < modifies.size() && modifies[mdx].F == i)
{
modify(modifies[mdx].S.F, Q + 1, modifies[mdx].S.S.S);
mdx++;
}
while (qdx < queries.size() && queries[qdx].F == i)
{
ans[queries[qdx].S.F] = color[bsearch(queries[qdx].S.S)];
qdx++;
}
}
for (int i = 1; i <= Q; i++)
if (ans[i] >= 0)
cout << ans[i] << '\n';
}
/*
3 4 5
1 2 3 1 50
1 1 2 4 50
3 2 51
1 1 1 3 50
3 1 100
*/
Compilation message
foodcourt.cpp: In function 'int main()':
foodcourt.cpp:77:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, std::pair<long long int, long long int> > > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
77 | while (mdx < modifies.size() && modifies[mdx].F == i)
| ~~~~^~~~~~~~~~~~~~~~~
foodcourt.cpp:82:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
82 | while (qdx < queries.size() && queries[qdx].F == i)
| ~~~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
5648 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1 ms |
468 KB |
Execution killed with signal 6 |
| 2 |
Halted |
0 ms |
0 KB |
- |
