#include<bits/stdc++.h>
#define ll long long
#define fi first
#define se second
using namespace std ;
const int N = (1 << 18) ;
ll n, m, q, sum[2 * N + 1], psh[2 * N + 1] ;
deque<pair<ll, ll>> d[N + 1] ;
void push(int l, int r, int v)
{
if(!psh[v])
return ;
int num = psh[v] ;
psh[v] = 0 ;
sum[v] += num * (r - l + 1) ;
if(l == r)
return ;
psh[2 * v] += num ;
psh[2 * v + 1] += num ;
}
void update(int l, int r, int l1, int r1, int num, int v)
{
push(l, r, v) ;
if(l > r1 || r < l1)
return ;
if(l1 <= l && r <= r1)
{
psh[v] = num ;
push(l, r, v) ;
return ;
}
int mid = (l + r) >> 1 ;
update(l, mid, l1, r1, num, v * 2) ;
update(mid + 1, r, l1, r1, num, v * 2 + 1) ;
sum[v] = sum[v * 2] + sum[v * 2 + 1] ;
}
int get_sum(int l, int r, int pos, int v)
{
if(l > pos || r < pos)
return 0 ;
if(l == r)
return sum[v] ;
int mid = (l + r) >> 1 ;
return get_sum(l, mid, pos, v * 2) + get_sum(mid + 1, r, pos, v * 2 + 1) ;
}
signed main()
{
// ios_base::sync_with_stdio( 0 ) ;
// cin.tie( 0 ) ;
// cout.tie( 0 ) ;
cin >> n >> m >> q ;
// if(n <= 2000 && m <= 2000 && q <= 2000)
// {
// while(q--)
// {
// ll type, l, r, c, k, a, b ;
// cin >> type ;
// if(type == 1)
// {
// cin >> l >> r >> c >> k ;
// for(ll i = l ; i <= r ; i++)
// d[i].push_back({c, k}) ;
// }
// if(type == 2)
// {
// cin >> l >> r >> k ;
// for(ll i = l ; i <= r ; i++)
// {
// ll sum = 0, k1 = k ;
// for(auto j : d[i])
// sum += j.se ;
// if(sum < k1)
// {
// d[i].clear() ;
// continue ;
// }
// while(k1)
// if(d[i][0].se <= k1)
// {
// k1 -= d[i][0].se ;
// d[i].pop_front() ;
// }
// else
// {
// pair<ll, ll> p = {d[i][0].fi, d[i][0].se - k1} ;
// d[i].pop_front() ;
// d[i].push_front(p) ;
// k1 = 0 ;
// }
// }
// }
// if(type == 3)
// {
// ll sum = 0, ans = 0 ;
// cin >> a >> b ;
// for(auto i : d[a])
// sum += i.se ;
// if(sum < b)
// {
// cout << "0\n" ;
// continue ;
// }
// for(auto i : d[a])
// if(i.se < b)
// b -= i.se ;
// else
// {
// ans = i.fi ;
// break ;
// }
// cout << ans << "\n" ;
// }
// }
// }
if(n <= 65000 && q <= 65000)
{
bool flag1 = 0 ;
ll type[q + 1], l[q + 1], r[q + 1], c[q + 1], k[q + 1], a[q + 1], b[q + 1] ;
for(ll i = 1 ; i <= q ; i++)
{
cin >> type[i] ;
if(type[i] == 1)
{
cin >> l[i] >> r[i] >> c[i] >> k[i] ;
if(r[i] - l[i] > 10 || k[i] != 1)
flag1 = 1 ;
}
if(type[i] == 2)
cin >> l[i] >> r[i] >> k[i] ;
if(type[i] == 3)
cin >> a[i] >> b[i] ;
}
if(!flag1)
{
for(ll i = 1 ; i <= q ; i++)
{
if(type[i] == 1)
{
for(ll j = l[i] ; j <= r[i] ; j++)
{
ll num = get_sum(1, N, j, 1) ;
if(num >= d[j].size())
d[j].clear() ;
else
{
for(int q = 1 ; q <= num ; q++)
d[j].pop_front() ;
}
update(1, N, j, j, 0, 1) ;
d[j].push_back({c[i], k[i]}) ;
}
}
if(type[i] == 2)
update(1, N, l[i], r[i], k[i], 1) ;
if(type[i] == 3)
{
ll num = get_sum(1, N, a[i], 1) ;
if(num >= d[a[i]].size())
d[a[i]].clear() ;
else
{
for(int j = 1 ; j <= num ; j++)
d[a[i]].pop_front() ;
}
update(1, N, a[i], a[i], 0, 1) ;
if(b[i] <= d[a[i]].size())
cout << d[a[i]][b[i] - 1].fi << '\n' ;
else
cout << "0\n" ;
}
// for(int i=1;i<=n;i++)
// {
// cout << i << '\n' ;
// for(auto j : d[i])
// cout << j.fi << ' ' << j.se << '\n' ;
// }
// cout << "___________\n" ;
}
return 0 ;
}
}
if(m == 1)
{
while(m--)
{
}
return 0 ;
}
return 0 ;
}
Compilation message
foodcourt.cpp: In function 'int main()':
foodcourt.cpp:142:32: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
142 | if(num >= d[j].size())
| ~~~~^~~~~~~~~~~~~~
foodcourt.cpp:158:28: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
158 | if(num >= d[a[i]].size())
| ~~~~^~~~~~~~~~~~~~~~~
foodcourt.cpp:166:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::deque<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
166 | if(b[i] <= d[a[i]].size())
| ~~~~~^~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
109 ms |
176716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
109 ms |
176716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
204 ms |
182480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
89 ms |
176744 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
109 ms |
176716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
133 ms |
179868 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
109 ms |
176716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
109 ms |
176716 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
