#include <bits/stdc++.h>
#ifdef NON_SUBMIT
#define TEST(n) (n)
#define tout cerr
#else
#define TEST(n) ((void)0)
#define tout cin
#endif
using namespace std;
struct Seg
{
long long mn, smn, lz, slz;
Seg() : mn(0), smn(0x7fffffffffffffffLL), lz(0), slz(-0x7fffffffffffffffLL) {}
Seg &operator =(const Seg &a) {
mn=a.mn;
smn=a.smn;
return *this;
}
};
const int SZ=1<<18;
const long long MAX=0x7fffffffffffffffLL;
Seg tree[2*SZ];
vector<tuple<int,int,long long>> L[2*SZ];
void update(int s, int e, int q, int c, int k)
{
for(s+=SZ,e+=SZ;s<=e;s>>=1,e>>=1) {
if(s&1) {
L[s].emplace_back(q,c,get<2>(L[s].back())+k);
s++;
}
if(~e&1) {
L[e].emplace_back(q,c,get<2>(L[e].back())+k);
e--;
}
}
}
Seg combine(const Seg &a, const Seg &b)
{
Seg c;
c.mn=min(a.mn,b.mn);
if(c.mn<max(a.mn,b.mn)) c.smn=max(a.mn,b.mn);
if(c.mn<a.smn) c.smn=max(c.smn,a.smn);
if(c.mn<b.smn) c.smn=max(c.smn,b.smn);
return c;
}
void lazy_propagation(int bit, int s, int e)
{
if(tree[bit].slz!=-MAX) {
if(s<e) {
if(max(tree[2*bit].slz,tree[2*bit].mn)+tree[2*bit].lz==tree[bit].mn) tree[2*bit].slz=tree[bit].slz-tree[2*bit].lz;
if(max(tree[2*bit+1].slz,tree[2*bit+1].mn)+tree[2*bit+1].lz==tree[bit].mn) tree[2*bit+1].slz=tree[bit].slz-tree[2*bit+1].lz;
}
tree[bit].mn=tree[bit].slz;
tree[bit].slz=-MAX;
}
tree[bit].mn+=tree[bit].lz;
if(tree[bit].smn<MAX) tree[bit].smn+=tree[bit].lz;
if(s<e) {
tree[2*bit].lz+=tree[bit].lz;
tree[2*bit+1].lz+=tree[bit].lz;
}
tree[bit].lz=0;
}
void add_tree(int n1, int n2, int v, int bit=1, int s=0, int e=SZ-1)
{
int m=(s+e)>>1;
lazy_propagation(bit,s,e);
if(n2<n1 || n2<s || e<n1) return;
if(n1<=s && e<=n2) {
tree[bit].lz=v;
lazy_propagation(bit,s,e);
return;
}
add_tree(n1,n2,v,2*bit,s,m);
add_tree(n1,n2,v,2*bit+1,m+1,e);
tree[bit]=combine(tree[2*bit],tree[2*bit+1]);
}
void set_tree(int n1, int n2, int bit=1, int s=0, int e=SZ-1)
{
int m=(s+e)>>1;
lazy_propagation(bit,s,e);
if(n2<n1 || n2<s || e<n1 || tree[bit].mn>=0) return;
if(n1<=s && e<=n2 && tree[bit].smn>0) {
tree[bit].slz=0;
lazy_propagation(bit,s,e);
return;
}
set_tree(n1,n2,2*bit,s,m);
set_tree(n1,n2,2*bit+1,m+1,e);
tree[bit]=combine(tree[2*bit],tree[2*bit+1]);
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
TEST(freopen("input.txt","r",stdin));
TEST(freopen("output.txt","w",stdout));
TEST(freopen("debug.txt","w",stderr));
int N, M, Q;
cin>>N>>M>>Q;
for(int i=2*SZ;--i;) L[i].emplace_back(0,0,0);
for(int i=1;i<=Q;i++) {
int t, a, c, d;
long long b;
cin>>t>>a>>b;
if(t==1) {
cin>>c>>d;
update(--a,--b,i,c,d);
add_tree(a,b,d);
}
else if(t==2) {
cin>>c;
add_tree(--a,--b,-c);
set_tree(a,b);
}
else {
long long tot;
int n=1, s=0, e=SZ-1; --a;
while(s<e) {
int m=(s+e)>>1;
lazy_propagation(n,s,e);
if(a<=m) tie(n,e)=make_pair(2*n,m);
else tie(n,s)=make_pair(2*n+1,m+1);
}
lazy_propagation(n,s,e);
if(tree[n].mn<b) {
cout<<"0\n";
continue;
}
for(tot=get<2>(L[n=SZ+a].back());n>>=1;) tot+=get<2>(L[n].back());
b+=tot-tree[SZ+a].mn;
s=1; e=i-1;
while(s<=e) {
int m=(s+e)>>1; tot=0; n=SZ+a;
for(;;) {
tot+=get<2>(*--upper_bound(L[n].begin(),L[n].end(),make_tuple(m,0,0)));
if(!(n>>=1)) break;
}
if(tot<b) s=m+1;
else e=m-1;
}
n=SZ+a; e=tot=0;
for(;;) {
auto v=*--upper_bound(L[n].begin(),L[n].end(),make_tuple(s,0,0));
if(get<0>(v)>tot) {
tot=get<0>(v);
e=get<1>(v);
}
if(!(n>>=1)) break;
}
cout<<e<<'\n';
}
}
return 0;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
45508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
45508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
227 ms |
48456 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Execution timed out |
1018 ms |
74856 KB |
Time limit exceeded |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
45508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
440 ms |
56304 KB |
Output is correct |
| 2 |
Correct |
452 ms |
57268 KB |
Output is correct |
| 3 |
Correct |
448 ms |
57728 KB |
Output is correct |
| 4 |
Correct |
315 ms |
54712 KB |
Output is correct |
| 5 |
Correct |
451 ms |
56488 KB |
Output is correct |
| 6 |
Correct |
479 ms |
58312 KB |
Output is correct |
| 7 |
Correct |
175 ms |
47224 KB |
Output is correct |
| 8 |
Correct |
168 ms |
47124 KB |
Output is correct |
| 9 |
Correct |
226 ms |
53084 KB |
Output is correct |
| 10 |
Correct |
212 ms |
55340 KB |
Output is correct |
| 11 |
Correct |
264 ms |
58748 KB |
Output is correct |
| 12 |
Correct |
270 ms |
58684 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
45508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
48 ms |
45508 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
