#include<bits/stdc++.h>
#define endl '\n'
#define ll long long
using namespace std;
const long long MAXN = 7e4+10;
void speed()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
}
long long n, m, q;
vector < pair < long long/**number*/, long long/**colour*/> > g[MAXN];
vector < pair < long long, long long > > pref[MAXN];
long long cutted[MAXN];
vector < pair < long long, long long > > lazy[MAXN * 4];
long long ql, qr, val;
long long find_pref(long long ttime, long long shop)
{
long long l = 0, r = pref[shop].size(), mid, ans = 0;
while(l <= r)
{
mid = (l + r)/2;
if(pref[shop][mid].second <= ttime)
{
ans = mid;
l = mid + 1;
}
else r = mid - 1;
}
return pref[shop][ans].first;
}
void push_lazy(long long i, long long l, long long r)
{
if(lazy[i].size() != 0 && l == r)
{
long long vall, timerr;
for (long long j = 0; j < lazy[i].size(); ++ j)
{
vall = lazy[i][j].first;
timerr = lazy[i][j].second;
cutted[l] += min(find_pref(timerr, l) - cutted[l], vall);
}
}
if(l != r)
{
for (long long j = 0; j < lazy[i].size(); ++ j)
{
lazy[2*i].push_back(lazy[i][j]);
lazy[2*i+1].push_back(lazy[i][j]);
}
}
lazy[i].clear();
}
long long tt;
void update(long long i, long long l, long long r)
{
push_lazy(i, l, r);
if(ql <= l && r <= qr)
{
lazy[i].push_back({val, tt});
push_lazy(i, l, r);
return;
}
if(qr < l || ql > r)return;
long long mid = (l + r)/2;
update(2*i, l, mid);
update(2*i+1, mid+1, r);
}
long long x;
long long query(long long i, long long l, long long r)
{
push_lazy(i, l, r);
if(l == r)
{
push_lazy(i, l, r);
return cutted[l];
}
long long mid = (l + r)/2;
if(x <= mid)return query(2*i, l, mid);
else return query(2*i+1, mid+1, r);
}
void solve()
{
cin >> n >> m >> q;
long long type, l, r, k, c;
for (long long i = 1; i <= n; ++ i)
{
pref[i].push_back({0, 0});
g[i].push_back({0, 0});
}
long long aa, bb;
for (long long i = 1; i <= q; ++ i)
{
cin >> type;
if(type == 1)
{
cin >> l >> r >> c >> k;
for (long long j = l; j <= r; ++ j)
{
g[j].push_back(make_pair(k, c));
pref[j].push_back(make_pair(pref[j].back().first+k, i));
}
}
else if(type == 2)
{
cin >> l >> r >> k;
ql = l;
qr = r;
val = k;
tt = i;
update(1, 1, n);
}
else
{
cin >> aa >> bb;
x = aa;
long long loose = query(1, 1, n);
// cout << loose << endl;
/// cout << "* " << cutted[aa] << " " << endl;
long long l = 0, r = pref[aa].size()-1, mid, ans = 0;
while(l <= r)
{
mid = (l + r)/2;
if(pref[aa][mid].first < bb + loose)
{
l = mid + 1;
}
else
{
ans = mid;
r = mid - 1;
}
}
cout << g[aa][ans].second << endl;
}
}
}
int main()
{
speed();
solve();
return 0;
}
Compilation message
foodcourt.cpp: In function 'void push_lazy(long long int, long long int, long long int)':
foodcourt.cpp:40:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
40 | for (long long j = 0; j < lazy[i].size(); ++ j)
| ~~^~~~~~~~~~~~~~~~
foodcourt.cpp:49:33: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
49 | for (long long j = 0; j < lazy[i].size(); ++ j)
| ~~^~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
27472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
27472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
281 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
18 ms |
30556 KB |
Execution killed with signal 11 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
27472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
471 ms |
524288 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
27472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
20 ms |
27472 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
