oj.uz

Submission #847427

# Submission time Handle Problem Language Result Execution time Memory
847427 2023-09-09T16:05:39 Z qwerasdfzxcl Mizuyokan 2 (JOI23_mizuyokan2) C++17
0 / 100
 4000 ms 221028 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;

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);
	// 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;

	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 (S[r-1]-S[l-1] > a[r]) ret = 2;
	if (S[r]-S[l] > a[l]) ret = 2;

	int nl = r+1, nr = l-1;
	for (int i=l+1;i<=min(l+30, r);i++) if (S[i-1]-S[l-1] > a[i]) {nl = i; break;}
	for (int i=r-1;i>=max(l, r-30);i--) if (S[r]-S[i] > 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;
	for (int i=1;i<=n+1;i++) prv[i] = go[i];
	init(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:148:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  148 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
mizuyokan2.cpp:149:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  149 |  for (int i=1;i<=n;i++) scanf("%d", a+i);
      |                         ~~~~~^~~~~~~~~~~
mizuyokan2.cpp:154:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  154 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
mizuyokan2.cpp:157:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  157 |   scanf("%d %d %d %d", &x, &y, &l, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 6.0

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

Subtask #2
0 / 9.0

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

Subtask #3
0 / 13.0

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

Subtask #4
0 / 32.0

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

Subtask #5
0 / 29.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 4444 KB Output is correct
2 Correct 1 ms 4444 KB Output is correct
3 Execution timed out 4035 ms 221028 KB Time limit exceeded
4 Halted 0 ms 0 KB -

Subtask #6
0 / 11.0

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