#include "bits/stdc++.h"
using namespace std;
// #define ORD_SET
// #define ROPE
#ifdef ORD_SET
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#endif
#ifdef ROPE
#include <ext/rope>
using namespace __gnu_cxx;
#endif
// #pragma comment(linker, "/stack:200000000")
// #pragma GCC optimize("Ofast")
// #pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
using ll = long long;
using ld = long double;
#define pb push_back
#define ff first
#define ss second
#define sz(x) (ll)(x).size()
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
// #define ll int
void freopen(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); }
void NotInteractive() { ios_base::sync_with_stdio(false); cin.tie(NULL); }
void pre(ll a) { cout<<fixed<<setprecision(a); }
ll bit(ll x) { return __builtin_popcountll(x); }
ll binpow(ll x, ll y, ll z) { ll pow = 1; while(y) { if(y&1) pow *= x, pow %= z; x *= x, x %= z; y >>= 1; } return pow; }
template<typename T> T gcd(T a, T b) { if(b==0) return a; return gcd(b, a%b); }
template<typename T> T lcm(T a, T b) { return a/gcd(a, b)*b; }
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
struct sn { ll l, r, x; }; // a.swap(b)
ll B = 316;
const ll mod = (ll)1e9+7;
const ll inf = (ll)1e18+7;
const ll MX = LLONG_MAX;
const ll MN = LLONG_MIN;
const ld P = acos(-1.0);
const ll N = (ll)3e5+5;
vector<pair<ll, ll>> v[N];
vector<ll> len(N);
ll t[N], l[N], r[N], c[N], k[N];
void kigash() {
ll n, m, q;
cin>>n>>m>>q;
if(n>2000) {
vector<ll> g[n+1];
while(q--) {
ll t, l, r, c, k;
cin>>t;
if(t==1) {
cin>>l>>r>>c>>k;
for(ll i=l; i<=r; i++) {
for(ll j=1; j<=k; j++) g[i].pb(c);
}
}
else if(t==2) {
cin>>l>>r>>k;
for(ll i=l; i<=r; i++) {
if(sz(g[i])<=k) g[i].clear();
else {
vector<ll> tmp;
for(ll j=k; j<sz(v[i]); j++) tmp.pb(g[i][j]);
g[i] = tmp;
}
}
}
else {
cin>>c>>k;
// cout<<sz(v[c])<<" ";
if(sz(g[c])>=k) cout<<g[c][k-1]<<"\n";
else cout<<"0\n";
}
return;
}
}
for(ll i=1; i<=q; i++) {
ll tmp = -1, lmp = -1, rmp = -1, cmp = -1, kmp = -1;
cin>>tmp;
if(tmp==1) cin>>lmp>>rmp>>cmp>>kmp;
else if(tmp==2) cin>>lmp>>rmp>>kmp;
else cin>>cmp>>kmp;
t[i] = tmp, l[i] = lmp, r[i] = rmp, c[i] = cmp, k[i] = kmp;
}
for(ll tt=1; tt<=q; tt++) {
// if(tt==3) {
// for(ll i=1; i<=n; i++) {
// for(auto x: v[i]) cout<<x.ff<<" "<<x.ss<<"\n";
// cout<<"\n";
// }
// return;
// }
if(t[tt]==1) {
for(ll i=l[tt]; i<=r[tt]; i++) v[i].pb({k[tt], c[tt]}), len[i] += k[tt];
}
else if(t[tt]==2) {
for(ll i=l[tt]; i<=r[tt]; i++) {
if(len[i]<=k[tt]) len[i] = 0, v[i].clear();
else {
vector<pair<ll, ll>> tmp;
ll f = 0;
len[i] -= k[tt];
for(ll j=0, sum = 0; j<sz(v[i]); j++) {
if(f) {
tmp.pb(v[i][j]);
continue;
}
sum += v[i][j].ff;
if(sum==k[tt]) f = 1;
else if(sum>k[tt]) {
tmp.pb({v[i][j].ff-(k[tt]-sum+v[i][j].ff), v[i][j].ss});
f = 1;
}
}
v[i] = tmp;
}
}
}
else {
if(len[c[tt]]>=k[tt]) {
for(ll i=0, sum = 0; i<sz(v[c[tt]]); i++) {
sum += v[c[tt]][i].ff;
if(sum>=k[tt]) {
cout<<v[c[tt]][i].ss<<"\n";
break;
}
}
}
else cout<<"0\n";
}
}
return;
}
signed main(/**/) {
// freopen("");
NotInteractive();
// precalc();
ll tt = 1;
// cin>>tt;
for(ll i=1; i<=tt; i++) kigash();
exit(0);
}
Compilation message
foodcourt.cpp: In function 'void freopen(std::string)':
foodcourt.cpp:31:33: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
31 | void freopen(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:31:75: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
31 | void freopen(string s) { freopen((s + ".in").c_str(), "r", stdin); freopen((s + ".out").c_str(), "w", stdout); }
| ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
10424 KB |
Output is correct |
| 2 |
Correct |
95 ms |
11000 KB |
Output is correct |
| 3 |
Correct |
201 ms |
21108 KB |
Output is correct |
| 4 |
Correct |
481 ms |
24592 KB |
Output is correct |
| 5 |
Correct |
6 ms |
9812 KB |
Output is correct |
| 6 |
Correct |
5 ms |
9812 KB |
Output is correct |
| 7 |
Execution timed out |
1091 ms |
27328 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
10424 KB |
Output is correct |
| 2 |
Correct |
95 ms |
11000 KB |
Output is correct |
| 3 |
Correct |
201 ms |
21108 KB |
Output is correct |
| 4 |
Correct |
481 ms |
24592 KB |
Output is correct |
| 5 |
Correct |
6 ms |
9812 KB |
Output is correct |
| 6 |
Correct |
5 ms |
9812 KB |
Output is correct |
| 7 |
Execution timed out |
1091 ms |
27328 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
11220 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
15016 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
10424 KB |
Output is correct |
| 2 |
Correct |
95 ms |
11000 KB |
Output is correct |
| 3 |
Correct |
201 ms |
21108 KB |
Output is correct |
| 4 |
Correct |
481 ms |
24592 KB |
Output is correct |
| 5 |
Correct |
6 ms |
9812 KB |
Output is correct |
| 6 |
Correct |
5 ms |
9812 KB |
Output is correct |
| 7 |
Execution timed out |
1091 ms |
27328 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
6 ms |
11220 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
10424 KB |
Output is correct |
| 2 |
Correct |
95 ms |
11000 KB |
Output is correct |
| 3 |
Correct |
201 ms |
21108 KB |
Output is correct |
| 4 |
Correct |
481 ms |
24592 KB |
Output is correct |
| 5 |
Correct |
6 ms |
9812 KB |
Output is correct |
| 6 |
Correct |
5 ms |
9812 KB |
Output is correct |
| 7 |
Execution timed out |
1091 ms |
27328 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
41 ms |
10424 KB |
Output is correct |
| 2 |
Correct |
95 ms |
11000 KB |
Output is correct |
| 3 |
Correct |
201 ms |
21108 KB |
Output is correct |
| 4 |
Correct |
481 ms |
24592 KB |
Output is correct |
| 5 |
Correct |
6 ms |
9812 KB |
Output is correct |
| 6 |
Correct |
5 ms |
9812 KB |
Output is correct |
| 7 |
Execution timed out |
1091 ms |
27328 KB |
Time limit exceeded |
| 8 |
Halted |
0 ms |
0 KB |
- |
