답안 #847405

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
847405	2023-09-09T15:30:48 Z	qwerasdfzxcl	Mizuyokan 2 (JOI23_mizuyokan2)	C++17	컴파일 오류	0 ms	0 KB

mizuyokan2

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

constexpr int INF1 = 1e9 + 100;

int n;
int a[250250];

int go[250250];
ll S[250250];

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;
		}

		if (i+50 < n) assert(go[i] <= n);
	}

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

int solve(int l, int r){
	if (r-l+1 < 3) return -INF1;
	int cnt = 0;
	for (int x=l,j=19;j>=0;j--) if (sp[x][j] <= r){
		x = sp[x][j];
		cnt |= 1<<j;
	}

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

void update(int x, int y){
	a[x] = y;
	init(n);
}

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 solve(int, int)':
mizuyokan2.cpp:34:34: error: 'sp' was not declared in this scope
   34 |  for (int x=l,j=19;j>=0;j--) if (sp[x][j] <= r){
      |                                  ^~
mizuyokan2.cpp: In function 'int main()':
mizuyokan2.cpp:62:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   62 |  scanf("%d", &n);
      |  ~~~~~^~~~~~~~~~
mizuyokan2.cpp:63:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   63 |  for (int i=1;i<=n;i++) scanf("%d", a+i);
      |                         ~~~~~^~~~~~~~~~~
mizuyokan2.cpp:68:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   68 |  scanf("%d", &q);
      |  ~~~~~^~~~~~~~~~
mizuyokan2.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |   scanf("%d %d %d %d", &x, &y, &l, &r);
      |   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~