oj.uz

Submission #851647

# Submission time Handle Problem Language Result Execution time Memory
851647 2023-09-20T10:17:15 Z MilosMilutinovic Fish 2 (JOI22_fish2) C++17
8 / 100
 4000 ms 35664 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) {
		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;
		}
	}
};

void build() {
	cnt::build(1,1,n);
	rep(i,1,n+1) sum::modify(i,a[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)) {
				//printf("add    %d %d\n",L,R);
				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)) {
				//printf("add    %d %d\n",L,R);
				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 nl=l,nr=r;
			rep(i,l+1,r+1) {
				if (a[i]>sum::get(l,i-1)) {
					nl=i;
				}
			}
			per(i,l,r) {
				if (a[i]>sum::get(i+1,r)) {
					nr=i;
				}
			}
			l=nl; r=nr;
			printf("%d\n",cnt::sol(l,r));
		}
	}
}

Compilation message

fish2.cpp: In function 'void segs::add(int, int, int, int, int, PII)':
fish2.cpp:54:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   54 |   int mid=l+r>>1;
      |           ~^~
fish2.cpp: In function 'void cnt::build(int, int, int)':
fish2.cpp:85:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |   int mid=l+r>>1;
      |           ~^~
fish2.cpp: In function 'void cnt::add(int, int, int, int, int, int)':
fish2.cpp:101:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  101 |   int mid=l+r>>1;
      |           ~^~
fish2.cpp: In function 'PII cnt::query(int, int, int, int, int)':
fish2.cpp:114:12: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  114 |   int mid=l+r>>1;
      |           ~^~
fish2.cpp: In function 'int main()':
fish2.cpp:164:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  164 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
fish2.cpp:166:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  166 |   scanf("%d",&a[i]);
      |   ~~~~~^~~~~~~~~~~~
fish2.cpp:169:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  169 |  scanf("%d",&q);
      |  ~~~~~^~~~~~~~~
fish2.cpp:172:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  172 |   scanf("%d",&op);
      |   ~~~~~^~~~~~~~~~
fish2.cpp:177:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  177 |    scanf("%d%d",&l,&r);
      |    ~~~~~^~~~~~~~~~~~~~

Subtask #1
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 22876 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 4 ms 22876 KB Output is correct
2 Correct 61 ms 35644 KB Output is correct
3 Correct 57 ms 34820 KB Output is correct
4 Correct 60 ms 35664 KB Output is correct
5 Correct 56 ms 34928 KB Output is correct
6 Correct 39 ms 33104 KB Output is correct
7 Correct 31 ms 31580 KB Output is correct
8 Correct 39 ms 33012 KB Output is correct
9 Correct 31 ms 31572 KB Output is correct
10 Correct 43 ms 33492 KB Output is correct
11 Correct 43 ms 32988 KB Output is correct
12 Correct 37 ms 32196 KB Output is correct
13 Correct 37 ms 32084 KB Output is correct
14 Correct 49 ms 33620 KB Output is correct
15 Correct 48 ms 33620 KB Output is correct

Subtask #3
0 / 12.0

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

Subtask #4
0 / 23.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 22876 KB Output is correct
2 Correct 61 ms 35644 KB Output is correct
3 Correct 57 ms 34820 KB Output is correct
4 Correct 60 ms 35664 KB Output is correct
5 Correct 56 ms 34928 KB Output is correct
6 Correct 39 ms 33104 KB Output is correct
7 Correct 31 ms 31580 KB Output is correct
8 Correct 39 ms 33012 KB Output is correct
9 Correct 31 ms 31572 KB Output is correct
10 Correct 43 ms 33492 KB Output is correct
11 Correct 43 ms 32988 KB Output is correct
12 Correct 37 ms 32196 KB Output is correct
13 Correct 37 ms 32084 KB Output is correct
14 Correct 49 ms 33620 KB Output is correct
15 Correct 48 ms 33620 KB Output is correct
16 Correct 5 ms 22872 KB Output is correct
17 Execution timed out 4019 ms 35268 KB Time limit exceeded
18 Halted 0 ms 0 KB -

Subtask #5
0 / 35.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 22876 KB Output is correct
2 Correct 61 ms 35644 KB Output is correct
3 Correct 57 ms 34820 KB Output is correct
4 Correct 60 ms 35664 KB Output is correct
5 Correct 56 ms 34928 KB Output is correct
6 Correct 39 ms 33104 KB Output is correct
7 Correct 31 ms 31580 KB Output is correct
8 Correct 39 ms 33012 KB Output is correct
9 Correct 31 ms 31572 KB Output is correct
10 Correct 43 ms 33492 KB Output is correct
11 Correct 43 ms 32988 KB Output is correct
12 Correct 37 ms 32196 KB Output is correct
13 Correct 37 ms 32084 KB Output is correct
14 Correct 49 ms 33620 KB Output is correct
15 Correct 48 ms 33620 KB Output is correct
16 Incorrect 5 ms 22872 KB Output isn't correct
17 Halted 0 ms 0 KB -

Subtask #6
0 / 17.0

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