Submission #851680

#	Time	Username	Problem	Language	Result	Execution time	Memory
851680		MilosMilutinovic	Fish 2 (JOI22_fish2)	C++14	31 / 100	1065 ms	54236 KiB

fish2

#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 (stderr)

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);
      |    ~~~~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 5
• Subtask 2: 8 / 8
• Subtask 3: 0 / 12
• Subtask 4: 23 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 17