#include <bits/stdc++.h>
using namespace std;
#define int ll
template <class T>
inline bool mnto(T& a, T b) {return a > b ? a = b, 1 : 0;}
template <class T>
inline bool mxto(T& a, T b) {return a < b ? a = b, 1: 0;}
#define REP(i, s, e) for (int i = s; i < e; i++)
#define RREP(i, s, e) for (int i = s; i >= e; i--)
typedef long long ll;
typedef long double ld;
#define MP make_pair
#define FI first
#define SE second
typedef pair<int, int> ii;
typedef pair<ll, ll> pll;
#define MT make_tuple
typedef tuple<int, int, int> iii;
#define ALL(_a) _a.begin(), _a.end()
#define pb push_back
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<ii> vii;
#ifdef DEBUG
#define debug(args...) _debug(args)
void _debug(const char* format, ...) {
va_list args;
va_start(args, format);
vprintf(format, args);
va_end(args);
}
#else
#define debug(args...)
#endif
#define INF 1000000005
#define LINF 1000000000000000005
#define MOD 1000000007
#define MAXN 300005
struct event {
int v, i, t;
};
struct query {
ll v;
int i;
};
int n, m, q;
vector<event> events[MAXN];
vector<query> queries[MAXN];
int grp[MAXN], ans[MAXN];
namespace st {
#define MLR int mid = lo + hi >> 1; int lc = u * 2, rc = u * 2 + 1
ll mn[MAXN * 4], lazy[MAXN * 4];
void propo(int u, int lo, int hi) {
if (lazy[u] == 0 || lo == hi) return;
MLR;
lazy[lc] += lazy[u];
lazy[rc] += lazy[u];
mn[lc] += lazy[u];
mn[rc] += lazy[u];
lazy[u] = 0;
}
void incre(int s, int e, int x, int u = 1, int lo = 1, int hi = q) {
if (lo >= s && hi <= e) {
lazy[u] += x;
mn[u] += x;
return;
}
propo(u, lo, hi);
MLR;
if (s <= mid) {
incre(s, e, x, lc, lo, mid);
}
if (e > mid) {
incre(s, e, x, rc, mid + 1, hi);
}
mn[u] = min(mn[lc], mn[rc]);
}
ll qmn(int s, int e, int u = 1, int lo = 1, int hi = q) {
if (lo >= s && hi <= e) {
return mn[u];
}
propo(u, lo, hi);
MLR;
if (e <= mid) {
return qmn(s, e, lc, lo, mid);
} else if (s > mid) {
return qmn(s, e, rc, mid + 1, hi);
} else {
return min(qmn(s, e, lc, lo, mid), qmn(s, e, rc, mid + 1, hi));
}
}
}
namespace fw {
ll v[MAXN];
void incre(int i, int x) {
for (; i <= q; i += i & -i) v[i] += x;
}
ll qsm(int i) {
ll res = 0;
for (; i > 0; i -= i & -i) res += v[i];
return res;
}
int get(ll x) {
int id = 0;
RREP (k, 25, 0) {
id ^= (1 << k);
if (id > q || v[id] >= x) {
id ^= (1 << k);
} else {
x -= v[id];
}
}
id++;
return id;
}
}
main() {
scanf("%lld%lld%lld", &n, &m, &q);
memset(ans, -1, sizeof ans);
REP (i, 1, q + 1) {
int t; scanf("%lld", &t);
if (t == 1) {
int l, r, c, k; scanf("%lld%lld%lld%lld", &l, &r, &c, &k);
events[l].pb({k, i, 0});
events[r + 1].pb({-k, i, 0});
grp[i] = c;
} else if (t == 2) {
int l, r, k; scanf("%lld%lld%lld", &l, &r, &k);
events[l].pb({-k, i, 1});
events[r + 1].pb({k, i, 1});
} else {
int a; ll b; scanf("%lld%lld", &a, &b);
queries[a].pb({b, i});
}
}
REP (i, 1, n + 1) {
for (event &e : events[i]) {
auto [v, i, t] = e;
st::incre(i, q, v);
if (!t) {
fw::incre(i, v);
}
}
for (query q : queries[i]) {
auto [v, i] = q;
ll rem = st::qmn(i, i) - st::qmn(1, i);
ll tot = fw::qsm(i);
ll rmv = tot - rem;
v += rmv;
if (v > tot) {
ans[i] = 0;
} else {
int id = fw::get(v);
ans[i] = grp[id];
}
}
}
REP (i, 1, q + 1) {
if (ans[i] == -1) continue;
printf("%lld\n", ans[i]);
}
return 0;
}
Compilation message
foodcourt.cpp: In function 'void st::propo(ll, ll, ll)':
foodcourt.cpp:58:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
58 | #define MLR int mid = lo + hi >> 1; int lc = u * 2, rc = u * 2 + 1
| ~~~^~~~
foodcourt.cpp:62:3: note: in expansion of macro 'MLR'
62 | MLR;
| ^~~
foodcourt.cpp:58:17: warning: unused variable 'mid' [-Wunused-variable]
58 | #define MLR int mid = lo + hi >> 1; int lc = u * 2, rc = u * 2 + 1
| ^~~
foodcourt.cpp:62:3: note: in expansion of macro 'MLR'
62 | MLR;
| ^~~
foodcourt.cpp: In function 'void st::incre(ll, ll, ll, ll, ll, ll)':
foodcourt.cpp:58:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
58 | #define MLR int mid = lo + hi >> 1; int lc = u * 2, rc = u * 2 + 1
| ~~~^~~~
foodcourt.cpp:76:3: note: in expansion of macro 'MLR'
76 | MLR;
| ^~~
foodcourt.cpp: In function 'll st::qmn(ll, ll, ll, ll, ll)':
foodcourt.cpp:58:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
58 | #define MLR int mid = lo + hi >> 1; int lc = u * 2, rc = u * 2 + 1
| ~~~^~~~
foodcourt.cpp:90:3: note: in expansion of macro 'MLR'
90 | MLR;
| ^~~
foodcourt.cpp: At global scope:
foodcourt.cpp:126:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
126 | main() {
| ^~~~
foodcourt.cpp: In function 'int main()':
foodcourt.cpp:127:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
127 | scanf("%lld%lld%lld", &n, &m, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:130:15: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
130 | int t; scanf("%lld", &t);
| ~~~~~^~~~~~~~~~~~
foodcourt.cpp:132:25: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
132 | int l, r, c, k; scanf("%lld%lld%lld%lld", &l, &r, &c, &k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:137:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
137 | int l, r, k; scanf("%lld%lld%lld", &l, &r, &k);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~
foodcourt.cpp:141:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
141 | int a; ll b; scanf("%lld%lld", &a, &b);
| ~~~~~^~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
16844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
16844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
119 ms |
23252 KB |
Output is correct |
| 2 |
Correct |
135 ms |
23476 KB |
Output is correct |
| 3 |
Correct |
108 ms |
23236 KB |
Output is correct |
| 4 |
Correct |
105 ms |
23240 KB |
Output is correct |
| 5 |
Correct |
135 ms |
23488 KB |
Output is correct |
| 6 |
Correct |
113 ms |
23504 KB |
Output is correct |
| 7 |
Correct |
56 ms |
22424 KB |
Output is correct |
| 8 |
Correct |
60 ms |
22536 KB |
Output is correct |
| 9 |
Correct |
106 ms |
23108 KB |
Output is correct |
| 10 |
Correct |
118 ms |
23460 KB |
Output is correct |
| 11 |
Correct |
115 ms |
23284 KB |
Output is correct |
| 12 |
Correct |
104 ms |
23492 KB |
Output is correct |
| 13 |
Correct |
97 ms |
22792 KB |
Output is correct |
| 14 |
Correct |
115 ms |
23340 KB |
Output is correct |
| 15 |
Correct |
142 ms |
23744 KB |
Output is correct |
| 16 |
Correct |
131 ms |
23748 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
550 ms |
40836 KB |
Output is correct |
| 2 |
Correct |
432 ms |
37552 KB |
Output is correct |
| 3 |
Correct |
641 ms |
42260 KB |
Output is correct |
| 4 |
Correct |
427 ms |
37948 KB |
Output is correct |
| 5 |
Incorrect |
543 ms |
38348 KB |
Output isn't correct |
| 6 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
16844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
102 ms |
22468 KB |
Output is correct |
| 2 |
Correct |
120 ms |
22912 KB |
Output is correct |
| 3 |
Incorrect |
112 ms |
22964 KB |
Output isn't correct |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
16844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
15 ms |
16844 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
