oj.uz

Submission #851669

# Submission time Handle Problem Language Result Execution time Memory
851669 2023-09-20T11:09:07 Z MilosMilutinovic Fish 2 (JOI22_fish2) C++17
8 / 100
 944 ms 48592 KB 
#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) {
			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);
		if (p.fi==0) {
			return p.se;
		} else {
			return 0;
		}
	}
};

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();
	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\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:154:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  154 |   int mid=l+r>>1;
      |           ~^~
fish2.cpp: In function 'pref::node pref::query(int, int, int, int, int)':
fish2.cpp:169:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  169 |   int mid=l+r>>1;
      |           ~^~
fish2.cpp: In function 'int main()':
fish2.cpp:228:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  228 |      int mid=low+high>>1;
      |              ~~~^~~~~
fish2.cpp:241:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  241 |      int mid=low+high>>1;
      |              ~~~^~~~~
fish2.cpp:211:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  211 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
fish2.cpp:213:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  213 |   scanf("%d",&a[i]);
      |   ~~~~~^~~~~~~~~~~~
fish2.cpp:216:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  216 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
fish2.cpp:219:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  219 |   scanf("%d",&op);
      |   ~~~~~^~~~~~~~~~
fish2.cpp:224:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  224 |    scanf("%d%d",&l,&r);
      |    ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 37464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 37468 KB Output is correct
2 Correct 76 ms 47452 KB Output is correct
3 Correct 69 ms 46796 KB Output is correct
4 Correct 72 ms 47844 KB Output is correct
5 Correct 70 ms 46916 KB Output is correct
6 Correct 52 ms 44624 KB Output is correct
7 Correct 44 ms 43944 KB Output is correct
8 Correct 66 ms 44624 KB Output is correct
9 Correct 43 ms 43856 KB Output is correct
10 Correct 56 ms 45392 KB Output is correct
11 Correct 52 ms 45168 KB Output is correct
12 Correct 48 ms 44392 KB Output is correct
13 Correct 50 ms 44368 KB Output is correct
14 Correct 61 ms 45616 KB Output is correct
15 Correct 61 ms 45364 KB Output is correct

Subtask #3
0 / 12.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 37464 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 37468 KB Output is correct
2 Correct 76 ms 47452 KB Output is correct
3 Correct 69 ms 46796 KB Output is correct
4 Correct 72 ms 47844 KB Output is correct
5 Correct 70 ms 46916 KB Output is correct
6 Correct 52 ms 44624 KB Output is correct
7 Correct 44 ms 43944 KB Output is correct
8 Correct 66 ms 44624 KB Output is correct
9 Correct 43 ms 43856 KB Output is correct
10 Correct 56 ms 45392 KB Output is correct
11 Correct 52 ms 45168 KB Output is correct
12 Correct 48 ms 44392 KB Output is correct
13 Correct 50 ms 44368 KB Output is correct
14 Correct 61 ms 45616 KB Output is correct
15 Correct 61 ms 45364 KB Output is correct
16 Correct 7 ms 37464 KB Output is correct
17 Incorrect 944 ms 48592 KB Output isn't correct
18 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 37468 KB Output is correct
2 Correct 76 ms 47452 KB Output is correct
3 Correct 69 ms 46796 KB Output is correct
4 Correct 72 ms 47844 KB Output is correct
5 Correct 70 ms 46916 KB Output is correct
6 Correct 52 ms 44624 KB Output is correct
7 Correct 44 ms 43944 KB Output is correct
8 Correct 66 ms 44624 KB Output is correct
9 Correct 43 ms 43856 KB Output is correct
10 Correct 56 ms 45392 KB Output is correct
11 Correct 52 ms 45168 KB Output is correct
12 Correct 48 ms 44392 KB Output is correct
13 Correct 50 ms 44368 KB Output is correct
14 Correct 61 ms 45616 KB Output is correct
15 Correct 61 ms 45364 KB Output is correct
16 Incorrect 7 ms 37464 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 37464 KB Output isn't correct
2 Halted 0 ms 0 KB -