oj.uz

Submission #847441

# Submission time Handle Problem Language Result Execution time Memory
847441 2023-09-09T16:22:29 Z qwerasdfzxcl Mizuyokan 2 (JOI23_mizuyokan2) C++17
32 / 100
 426 ms 225616 KB 
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

constexpr int INF1 = 1e9 + 100;

int n;
int a[250250];

int go[250250], sp[250250][20];
ll S[250250];

struct Node{
	array<int, 2> f[51];
	int pos, sz;

	Node(){}
	Node(int _pos, int nxt){
		f[0] = {nxt, 1};
		pos = _pos;
		sz = 1;
	}
};

array<int, 2> operator + (const array<int, 2> &x, int y){
	return {x[0], x[1]+y};
}

void merge(Node &P, const Node &L, const Node &R){
	P.sz = 0;
	for (int i=0;i<L.sz;i++){
		if (L.f[i][0] >= R.pos + R.sz) P.f[P.sz++] = L.f[i];
		else P.f[P.sz++] = R.f[L.f[i][0]-R.pos] + L.f[i][1];
	}

	for (int i=0;i<R.sz;i++){
		if (P.sz==51) return;
		P.f[P.sz++] = R.f[i];
	}
}

void push(Node &L, const Node &R){
	for (int i=0;i<L.sz;i++) if (L.f[i][0] < R.pos + R.sz) L.f[i] = R.f[L.f[i][0]-R.pos] + L.f[i][1];
	for (int i=0;i<R.sz;i++){
		if (L.sz==51) return;
		L.f[L.sz++] = R.f[i];
	}
}

struct Seg{
	Node tree[1101000], ret;

	void init(int i, int l, int r){
		if (l==r) {tree[i] = Node(l, go[l]); return;}
		
		int m = (l+r)>>1;
		init(i<<1, l, m); init(i<<1|1, m+1, r);

		tree[i].pos = l;
		merge(tree[i], tree[i<<1], tree[i<<1|1]);
	}

	void update(int i, int l, int r, int s, int e){
		if (r<s || e<l) return;
		if (l==r){
			tree[i] = Node(l, go[l]);
			return;
		}

		int m = (l+r)>>1;
		update(i<<1, l, m, s, e); update(i<<1|1, m+1, r, s, e);
		merge(tree[i], tree[i<<1], tree[i<<1|1]);
	}

	void query(int i, int l, int r, int s, int e){
		if (r<s || e<l) return;
		if (s<=l && r<=e){
			push(ret, tree[i]);
			return;
		}

		int m = (l+r)>>1;
		query(i<<1, l, m, s, e); query(i<<1|1, m+1, r, s, e);
	}
}tree;

struct Seg2{
	ll tree[500500];
	int sz;

	void init(int n){
		sz = n;
		for (int i=sz;i<sz*2;i++) tree[i] = a[i-sz];
		for (int i=sz-1;i;i--) tree[i] = tree[i<<1] + tree[i<<1|1];
	}

	void update(int p, int x){
		p += sz;
		tree[p] = x;
		for (p>>=1;p;p>>=1) tree[p] = tree[p<<1] + tree[p<<1|1];
	}

	ll query(int l, int r){
		r++;
		ll ret = 0;
		for (l+=sz, r+=sz;l<r;l>>=1, r>>=1){
			if (l&1) ret += tree[l++];
			if (r&1) ret += tree[--r];
		}

		return ret;
	}
}tree2;

void init(int n){
	for (int i=1;i<=n;i++) S[i] = S[i-1] + a[i];

	go[n+1] = n+1;
	for (int i=1;i<=n;i++){
		go[i] = n+1;
		for (int j=i+2;j<=min(i+50, n);j++) if (S[j-1] - S[i] > max(a[i], a[j])){
			go[i] = j;
			break;
		}
	}

	for (int i=n;i;i--) go[i] = min(go[i], go[i+1]);

	tree.init(1, 1, n);
	tree2.init(n+1);
	// for (int i=n;i;i--) assert(go[i] - i <= 50);

	// for (int i=1;i<=n+1;i++) sp[i][0] = go[i];
	// for (int j=1;j<20;j++){
	// 	for (int i=1;i<=n+1;i++) sp[i][j] = sp[sp[i][j-1]][j-1];
	// }
}

int solve(int l, int r){
	if (r-l+1 < 3) return -INF1;
	
	int cnt = 0;
	tree.ret.sz = 0;
	tree.ret.pos = l;
	tree.query(1, 1, n, l, r);

	for (int i=0;i<tree.ret.sz;i++) cnt = max(cnt, tree.ret.f[i][1]-1);

	return cnt * 2 + 1;
}

int query(int l, int r){
	int ret = 1;
	if (l==r) return ret;
	if (tree2.query(l, r-1) > a[r]) ret = 2;
	if (tree2.query(l+1, r) > a[l]) ret = 2;

	int nl = r+1, nr = l-1;
	ll sum = a[l];
	for (int i=l+1;i<=min(l+30, r);sum += a[i++]) if (sum > a[i]) {nl = i; break;}
	sum = a[r];
	for (int i=r-1;i>=max(l, r-30);sum += a[i--]) if (sum > a[i]) {nr = i; break;}
	if (nl <= nr) ret = 3;

	return max({ret, solve(l, r), solve(nl, r) + 1, solve(l, nr) + 1, solve(nl, nr) + 2});
}

int prv[250250];
void update(int x, int y){
	a[x] = y;
	tree2.update(x, y);
	// for (int i=1;i<=n+1;i++) prv[i] = go[i];
	// init(n);

	for (int i=x;i>=max(1, x-50);i--){
		go[i] = go[i+1];
		ll sum = a[i+1];
		for (int j=i+2;j<=min(i+50, go[i+1]-1);sum += a[j++]) if (sum > max(a[i], a[j])){
			go[i] = j;
			break;
		}
	}

	for (int i=1;i<=n;i++) printf("%d ", go[i]);
	printf("\n");
	// init(n);
	// for (int i=1;i<=n;i++) printf("%d ", go[i]);
	// printf("\n");

	tree.update(1, 1, n, 1, n);

	// for (int i=1;i<=n+1;i++) if (prv[i]!=go[i]) assert(x-50 <= i && i <= x);
}

int main(){
	scanf("%d", &n);
	for (int i=1;i<=n;i++) scanf("%d", a+i);

	init(n);

	int q;
	scanf("%d", &q);
	while(q--){
		int x, y, l, r;
		scanf("%d %d %d %d", &x, &y, &l, &r);
		
		if (a[x]!=y) update(x, y);

		l++;
		printf("%d\n", query(l, r));
	}
}

Compilation message

mizuyokan2.cpp: In function 'int main()':
mizuyokan2.cpp:197:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  197 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
mizuyokan2.cpp:198:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  198 |  for (int i=1;i<=n;i++) scanf("%d", a+i);
      |                         ~~~~~^~~~~~~~~~~
mizuyokan2.cpp:203:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  203 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
mizuyokan2.cpp:206:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  206 |   scanf("%d %d %d %d", &x, &y, &l, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Incorrect 1 ms 6488 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Incorrect 1 ms 6488 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Incorrect 1 ms 6488 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
32.0 / 32.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Correct 213 ms 224748 KB Output is correct
3 Correct 259 ms 225104 KB Output is correct
4 Correct 287 ms 225108 KB Output is correct
5 Correct 221 ms 225104 KB Output is correct
6 Correct 426 ms 225616 KB Output is correct
7 Correct 402 ms 225104 KB Output is correct
8 Correct 413 ms 225104 KB Output is correct
9 Correct 385 ms 225104 KB Output is correct
10 Correct 369 ms 225104 KB Output is correct
11 Correct 409 ms 225232 KB Output is correct
12 Correct 407 ms 225228 KB Output is correct
13 Correct 418 ms 225092 KB Output is correct
14 Correct 410 ms 225564 KB Output is correct
15 Correct 404 ms 225252 KB Output is correct
16 Correct 404 ms 225284 KB Output is correct
17 Correct 145 ms 225104 KB Output is correct
18 Correct 391 ms 225104 KB Output is correct

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Incorrect 1 ms 6488 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 6488 KB Output is correct
2 Incorrect 1 ms 6488 KB Output isn't correct
3 Halted 0 ms 0 KB -