#include <bits/stdc++.h>
using namespace std;
#define rep(i,a,n) for (int i=a;i<n;i++)
#define per(i,a,n) for (int i=n-1;i>=a;i--)
#define pb push_back
#define eb emplace_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define fi first
#define se second
#define SZ(x) ((int)(x).size())
typedef vector<int> VI;
typedef basic_string<int> B;
typedef long long ll;
typedef pair<int,int> PII;
typedef double db;
mt19937 mrand(random_device{}());
const ll mod=1000000007;
int rnd(int x) { return mrand() % x;}
ll powmod(ll a,ll b) {ll res=1;a%=mod; assert(b>=0); for(;b;b>>=1){if(b&1)res=res*a%mod;a=a*a%mod;}return res;}
ll gcd(ll a,ll b) { return b?gcd(b,a%b):a;}
// head
const int N=100100;
const int M=8*N;
const int inf=(int)1e9;
int n,q,a[N];
namespace sum {
ll c[N];
void modify(int p,int v) {
for (;p<N;p+=p&-p) c[p]+=v;
}
ll get(int p) {
ll r=0;
for (;p>0;p-=p&-p) r+=c[p];
return r;
}
ll get(int l,int r) {
if (l>r) {
return 0ll;
}
return get(r)-get(l-1);
}
};
namespace segs {
vector<PII> st[M];
void add(int x,int l,int r,int ql,int qr,PII p) {
if (l>r||l>qr||r<ql) {
return;
}
if (ql<=l&&r<=qr) {
st[x].pb(p);
return;
}
int mid=l+r>>1;
add(x*2,l,mid,ql,qr,p);
add(x*2+1,mid+1,r,ql,qr,p);
}
};
namespace cnt {
PII st[M];
int lzy[M];
void push(int x) {
st[x*2].fi+=lzy[x];
st[x*2+1].fi+=lzy[x];
lzy[x*2]+=lzy[x];
lzy[x*2+1]+=lzy[x];
lzy[x]=0;
}
PII mrg(PII a,PII b) {
PII r;
r.fi=min(a.fi,b.fi);
r.se=(a.fi==r.fi?a.se:0)+(b.fi==r.fi?b.se:0);
return r;
}
void pull(int x) {
st[x]=mrg(st[x*2],st[x*2+1]);
}
void build(int x,int l,int r) {
if (l==r) {
st[x].fi=0;
st[x].se=1;
return;
}
int mid=l+r>>1;
build(x*2,l,mid);
build(x*2+1,mid+1,r);
pull(x);
}
void add(int x,int l,int r,int ql,int qr,int v) {
if (l>r||l>qr||r<ql||ql>qr) {
return;
}
if (ql<=l&&r<=qr) {
st[x].fi+=v;
lzy[x]+=v;
push(x);
return;
}
push(x);
int mid=l+r>>1;
add(x*2,l,mid,ql,qr,v);
add(x*2+1,mid+1,r,ql,qr,v);
pull(x);
}
PII query(int x,int l,int r,int ql,int qr) {
if (l>r||l>qr||r<ql) {
return mp(inf,0);
}
if (ql<=l&&r<=qr) {
return st[x];
}
push(x);
int mid=l+r>>1;
auto qvl=query(x*2,l,mid,ql,qr);
auto qvr=query(x*2+1,mid+1,r,ql,qr);
pull(x);
return mrg(qvl,qvr);
}
int sol(int l,int r) {
auto p=query(1,1,n,l,r);
return p.se;
}
};
namespace pref {
struct node {
ll vl,vr;
node(ll _vl=0,ll _vr=0) : vl(_vl),vr(_vr) {}
};
node st[M];
node mrg(node a,node b) {
node r;
r.vl=max(a.vl,b.vl);
r.vr=max(a.vr,b.vr);
return r;
}
void pull(int x) {
st[x]=mrg(st[x*2],st[x*2+1]);
}
void modify(int x,int l,int r,int p) {
if (l==r) {
st[x].vl=a[p]-sum::get(1,p-1);
st[x].vr=a[p]-sum::get(p+1,N-1);
return;
}
int mid=l+r>>1;
if (p<=mid) {
modify(x*2,l,mid,p);
} else {
modify(x*2+1,mid+1,r,p);
}
pull(x);
}
node query(int x,int l,int r,int ql,int qr) {
if (l>r||l>qr||r<ql||ql>qr) {
return node(-inf*1ll*inf,-inf*1ll*inf);
}
if (ql<=l&&r<=qr) {
return st[x];
}
int mid=l+r>>1;
return mrg(query(x*2,l,mid,ql,qr),query(x*2+1,mid+1,r,ql,qr));
}
};
void build() {
cnt::build(1,1,n);
rep(i,1,n+1) {
sum::modify(i,a[i]);
}
rep(i,1,n+1) {
pref::modify(1,1,n,i);
}
stack<int> stk;
rep(i,1,n+1) {
while (SZ(stk)>0&&a[i]>a[stk.top()]) {
int L=stk.top();
int R=i;
if (L!=R-1&&min(a[L],a[R])>sum::get(L+1,R-1)) {
segs::add(1,1,n,L,R,mp(L,R));
cnt::add(1,1,n,L+1,R-1,1);
}
stk.pop();
}
stk.push(i);
}
while (SZ(stk)) stk.pop();
rep(i,1,n+1) {
while (SZ(stk)>0&&a[i]>=a[stk.top()]) {
int L=stk.top();
int R=i;
if (L!=R-1&&min(a[L],a[R])>sum::get(L+1,R-1)) {
segs::add(1,1,n,L,R,mp(L,R));
cnt::add(1,1,n,L+1,R-1,1);
}
stk.pop();
}
stk.push(i);
}
while (SZ(stk)) stk.pop();
per(i,1,n+1) {
while (SZ(stk)>0&&a[i]>a[stk.top()]) {
int L=i;
int R=stk.top();
if (L!=R-1&&min(a[L],a[R])>sum::get(L+1,R-1)) {
segs::add(1,1,n,L,R,mp(L,R));
cnt::add(1,1,n,L+1,R-1,1);
}
stk.pop();
}
stk.push(i);
}
per(i,1,n+1) {
while (SZ(stk)>0&&a[i]>=a[stk.top()]) {
int L=i;
int R=stk.top();
if (L!=R-1&&min(a[L],a[R])>sum::get(L+1,R-1)) {
segs::add(1,1,n,L,R,mp(L,R));
cnt::add(1,1,n,L+1,R-1,1);
}
stk.pop();
}
stk.push(i);
}
}
int main() {
scanf("%d",&n);
rep(i,1,n+1) {
scanf("%d",&a[i]);
}
build();
scanf("%d",&q);
while (q--) {
int op;
scanf("%d",&op);
if (op==1) {
} else {
int l,r;
scanf("%d%d",&l,&r);
{
int low=l,high=r,pos=l;
while (low<=high) {
int mid=low+high>>1;
if (pref::query(1,1,n,mid,r).vl+sum::get(1,l-1)>0) {
pos=mid;
low=mid+1;
} else {
high=mid-1;
}
}
l=pos;
}
{
int low=l,high=r,pos=r;
while (low<=high) {
int mid=low+high>>1;
if (pref::query(1,1,n,l,mid).vr+sum::get(r+1,n)>0) {
pos=mid;
high=mid-1;
} else {
low=mid+1;
}
}
r=pos;
}
printf("%d %d\n",l,r);
printf("%d\n",cnt::sol(l,r));
}
}
}
Compilation message
fish2.cpp: In function 'void segs::add(int, int, int, int, int, PII)':
fish2.cpp:57:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
57 | int mid=l+r>>1;
| ~^~
fish2.cpp: In function 'void cnt::build(int, int, int)':
fish2.cpp:88:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
88 | int mid=l+r>>1;
| ~^~
fish2.cpp: In function 'void cnt::add(int, int, int, int, int, int)':
fish2.cpp:104:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
104 | int mid=l+r>>1;
| ~^~
fish2.cpp: In function 'PII cnt::query(int, int, int, int, int)':
fish2.cpp:117:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
117 | int mid=l+r>>1;
| ~^~
fish2.cpp: In function 'void pref::modify(int, int, int, int)':
fish2.cpp:150:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
150 | int mid=l+r>>1;
| ~^~
fish2.cpp: In function 'pref::node pref::query(int, int, int, int, int)':
fish2.cpp:165:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
165 | int mid=l+r>>1;
| ~^~
fish2.cpp: In function 'int main()':
fish2.cpp:249:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
249 | int mid=low+high>>1;
| ~~~^~~~~
fish2.cpp:262:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
262 | int mid=low+high>>1;
| ~~~^~~~~
fish2.cpp:232:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
232 | scanf("%d",&n);
| ~~~~~^~~~~~~~~
fish2.cpp:234:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
234 | scanf("%d",&a[i]);
| ~~~~~^~~~~~~~~~~~
fish2.cpp:237:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
237 | scanf("%d",&q);
| ~~~~~^~~~~~~~~
fish2.cpp:240:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
240 | scanf("%d",&op);
| ~~~~~^~~~~~~~~~
fish2.cpp:245:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
245 | scanf("%d%d",&l,&r);
| ~~~~~^~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
37464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
37464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
37464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
37464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
37464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
7 ms |
37464 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
