#include <bits/stdc++.h>
#define int ll
#define ll long long
using namespace std;
const int nmax = 25e4 + 5;
#define lsb(x) (x & (-x))
struct AIB {
int tree[nmax];
int len;
void init(int nlen) {
len = nlen;
memset(tree, 0, sizeof(tree));
}
int query(int poz) {
int sum = 0;
while(poz > 0)
sum += tree[poz], poz -= lsb(poz);
return sum;
}
void upd(int poz, int val) {
while(poz <= len)
tree[poz] += val, poz += lsb(poz);
}
void upd(int l, int r, int val) {
upd(l, val);
upd(r + 1, -val);
}
};
int n, m, q;
namespace {
namespace AINT { // mai mult ca sigur nu asa se scrie Beats ;-;
AIB total;
vector<int> sus;
struct Node {
ll min1, min2, lazy;
Node operator + (const Node& x) const {
Node rez;
rez.lazy = 0; //??
sus.resize(4);
sus[0] = min1;
sus[1] = min2;
sus[2] = x.min2;
sus[3] = x.min1;
sort(sus.begin(), sus.end());
sus.resize(distance(sus.begin(), unique(sus.begin(), sus.end())));
rez.min1 = sus[0];
rez.min2 = sus[1];
return rez;
}
} aint[nmax * 4];
void pushmin(int node, ll val) {
aint[node].min1 = max(aint[node].min1, val);
}
void pushsum(int node, int cl, int cr) {
aint[node].min1 += aint[node].lazy;
aint[node].min2 += aint[node].lazy;
if(cl != cr) {
aint[2 * node].lazy += aint[node].lazy;
aint[2 * node + 1].lazy += aint[node].lazy;
}
aint[node].lazy = 0;
}
void prop(int node, int cl, int cr, ll val) {
pushsum(node, cl, cr);
pushmin(node, val);
if(cl == cr)
return;
int mid = cl + cr >> 1;
pushsum(2 * node, cl, mid);
pushmin(2 * node, val);
pushsum(2 * node + 1, mid + 1, cr);
pushmin(2 * node + 1, val);
}
void addv(int l, int r, ll val, int node = 1, int cl = 1, int cr = n) {
prop(node, cl, cr, -1e15 - 5);
if(l <= cl && cr <= r) {
aint[node].lazy += val;
prop(node, cl, cr, -1e15 - 5);
return;
}
if(r < cl || cr < l)
return;
int mid = cl + cr >> 1;
addv(l, r, val, 2 * node, cl, mid);
addv(l, r, val, 2 * node + 1, mid + 1, cr);
aint[node] = aint[2 * node] + aint[2 * node + 1];
}
void chmin(int l, int r, int node = 1, int cl = 1, int cr = n) {
prop(node, cl, cr, -1e15 - 5);
if(r < cl || cr < l || aint[node].min1 >= 0)
return;
if(l <= cl && cr <= r && aint[node].min2 >= 0) {
//cerr << "+ " << l << ' ' << cl << ' ' << cr << ' ' << r << ' '<< aint[node].min1 << ' ' << aint[node].min2 << '\n';
prop(node, cl, cr, 0);
//cerr << "+ " << cl << ' ' << cr << ' '<< aint[node].min1 << ' ' << aint[node].min2 << '\n';
return;
}
int mid = cl + cr >> 1;
chmin(l, r, 2 * node, cl, mid);
chmin(l, r, 2 * node + 1, mid + 1, cr);
aint[node] = aint[2 * node] + aint[2 * node + 1];
return;
}
int getval(int poz, int node = 1, int cl = 1, int cr = n) {
prop(node, cl, cr, aint[node].min1);
if(cl == cr)
return aint[node].min1;
int mid = cl + cr >> 1;
if(poz <= mid)
return getval(poz, 2 * node, cl, mid);
return getval(poz, 2 * node + 1, mid + 1, cr);
}
void add(int l, int r, ll val) {
addv(l, r, val);
total.upd(l, r, max(0LL, val));
}
int query(int queue, int poz) {
int all = total.query(queue);
int current = getval(queue);
//cout << all << ' ' << current << ' ' << poz << '\n';
if(poz > current)
return -1;
return all - current + poz;
}
void construct(int node = 1, int cl = 1, int cr = n) {
aint[node].min2 = 1e15 + 15;
if(cl == cr)
return;
int mid = cl + cr >> 1;
construct(2 * node, cl, mid);
construct(2 * node + 1, mid + 1, cr);
}
}
namespace CONCRETE { // AINT persistent sau AINT cu Treap (sau cu sume partiale, ce destept eram in trecut lmfao) in nod sau Cautare Binara in Paralel
// aici voi incerca Cautare Binara in paralel
struct Query {
int temp, queue, poz, iter;
bool operator < (const Query& x) const { return temp < x.temp; }
};
int sol[nmax];
AIB contor;
vector<Query> constqs, qs;
vector< tuple<int,int, int, int> > update;
void tour() {
int i = 0, ptr = 0;
contor.init(n + 2);
sort(qs.begin(), qs.end());
for(auto [l, r, dim, color] : update) {
contor.upd(l, r, dim);
i++;
while(qs.size() > ptr && qs[ptr].temp < i) {
if(contor.query(qs[ptr].queue) < qs[ptr].poz)
sol[qs[ptr].iter] = qs[ptr].temp;
ptr++;
}
}
}
void print() {
for(int i = 0; i < qs.size(); i++) {
//cerr << qs[i].poz << ' ' << qs[i].temp << '\n';
if(qs[i].poz == -1)
cout << "0\n";
else
cout << get<3>(update[sol[i] + 1]) << '\n';
}
}
void cbin() {
for(int i = 0; i < constqs.size(); i++)
sol[i] = -1;
qs.resize(constqs.size());
for(int i = 17; i >= 0; i--) {
for(int j = 0; j < qs.size(); j++)
qs[j] = constqs[j], qs[j].temp = sol[j] + (1 << i);
tour();
}
print();
}
}
namespace READ {
void read() {
cin >> n >> m >> q;
AINT::construct();
AINT::total.init(n + 1);
ll t, l, r, c, k;
for(int i = 0; i < q; i++) {
cin >> t;
if(t == 1) {
cin >> l >> r >> c >> k;
CONCRETE::update.push_back({l, r, k, c});
AINT::add(l, r, k);
}
else if(t == 2) {
cin >> l >> r >> c;
AINT::add(l, r, -c);
AINT::chmin(l, r);
}
else {
cin >> l >> r;
k = AINT::query(l, r);
//cout << k << '\n';
CONCRETE::constqs.push_back(CONCRETE::Query{1097, l, k, CONCRETE::constqs.size()});
}
}
}
}
}
signed main() {
::READ::read();
::CONCRETE::cbin();
return 0;
}
Compilation message
foodcourt.cpp: In function 'void {anonymous}::AINT::prop(long long int, long long int, long long int, long long int)':
foodcourt.cpp:72:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
72 | int mid = cl + cr >> 1;
| ~~~^~~~
foodcourt.cpp: In function 'void {anonymous}::AINT::addv(long long int, long long int, long long int, long long int, long long int, long long int)':
foodcourt.cpp:87:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
87 | int mid = cl + cr >> 1;
| ~~~^~~~
foodcourt.cpp: In function 'void {anonymous}::AINT::chmin(long long int, long long int, long long int, long long int, long long int)':
foodcourt.cpp:103:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
103 | int mid = cl + cr >> 1;
| ~~~^~~~
foodcourt.cpp: In function 'long long int {anonymous}::AINT::getval(long long int, long long int, long long int, long long int)':
foodcourt.cpp:113:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
113 | int mid = cl + cr >> 1;
| ~~~^~~~
foodcourt.cpp: In function 'void {anonymous}::AINT::construct(long long int, long long int, long long int)':
foodcourt.cpp:134:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
134 | int mid = cl + cr >> 1;
| ~~~^~~~
foodcourt.cpp: In function 'void {anonymous}::CONCRETE::tour()':
foodcourt.cpp:153:16: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
153 | for(auto [l, r, dim, color] : update) {
| ^
foodcourt.cpp:156:25: warning: comparison of integer expressions of different signedness: 'std::vector<{anonymous}::CONCRETE::Query>::size_type' {aka 'long unsigned int'} and 'long long int' [-Wsign-compare]
156 | while(qs.size() > ptr && qs[ptr].temp < i) {
| ~~~~~~~~~~^~~~~
foodcourt.cpp: In function 'void {anonymous}::CONCRETE::print()':
foodcourt.cpp:164:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<{anonymous}::CONCRETE::Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
164 | for(int i = 0; i < qs.size(); i++) {
| ~~^~~~~~~~~~~
foodcourt.cpp: In function 'void {anonymous}::CONCRETE::cbin()':
foodcourt.cpp:173:24: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<{anonymous}::CONCRETE::Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
173 | for(int i = 0; i < constqs.size(); i++)
| ~~^~~~~~~~~~~~~~~~
foodcourt.cpp:177:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<{anonymous}::CONCRETE::Query>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
177 | for(int j = 0; j < qs.size(); j++)
| ~~^~~~~~~~~~~
foodcourt.cpp: In function 'void {anonymous}::READ::read()':
foodcourt.cpp:206:89: warning: narrowing conversion of '{anonymous}::CONCRETE::constqs.std::vector<{anonymous}::CONCRETE::Query>::size()' from 'std::vector<{anonymous}::CONCRETE::Query>::size_type' {aka 'long unsigned int'} to 'long long int' [-Wnarrowing]
206 | CONCRETE::constqs.push_back(CONCRETE::Query{1097, l, k, CONCRETE::constqs.size()});
| ~~~~~~~~~~~~~~~~~~~~~~^~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
4360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
4360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
270 ms |
11044 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1086 ms |
25844 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
4360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
218 ms |
12052 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
4360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
8 ms |
4360 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
