제출 #1206956

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1206956		salmon	Mizuyokan 2 (JOI23_mizuyokan2)	C++20	0 / 100	26 ms	18500 KiB

mizuyokan2

#include <bits/stdc++.h>
using namespace std;

int N;
int lst[250100];
int Q;
vector<long long int> pre;

struct node{
	
	int s,e,m;
	node *l, *r;
	int v = 0;
	
	node(int S, int E){
		s = S;
		e = E;
		m = (s + e)/2;
		
		if(s != e){
			l = new node(s,m);
			r = new node(m + 1, e);
		}
	}
	
	void update(int i, int k){
		if(s == e){
			v = max(v,k);
			return;
		}
		
		if(i <= m) l -> update(i,k);
		if(m < i) r -> update(i,k);
		
		v = max(l -> v, r -> v);
	}
	
	int query(int S, int E){
		if(S <= s && e <= E) return v;
		
		int V = 0;
		
		if(S <= m) V = l -> query(S,E);		
		if(m < E) V = max(V, r -> query(S,E));
		
		return V;
	}	
}*root;

int main(){
	
	scanf(" %d",&N);
	
	for(int i = 1; i <= N; i++){
		scanf(" %d",&lst[i]);
	}
	
	root = new node(0,N-1);
	
	scanf(" %d",&Q);
	
	if(Q > 10) assert (1 == 2);
	
	for(int i = 0; i < Q; i++){
		pre.clear();
		
		int X,Y,A,B;
		
		scanf(" %d",&X);
		scanf(" %d",&Y);
		scanf(" %d",&A);
		scanf(" %d",&B);
			
		lst[X] = Y;
		
		pre.push_back(0);
		
		for(int i = A + 1; i <= B; i++){
			pre.push_back(pre.back() + lst[i]);
		}
		
		int memo[N + 5];
		vector<int> proc[N + 5];
		
		for(int i = 0; i <= B - A; i++){
			memo[i] = 0;
		}
		
		proc[2].push_back(0);
		root = new node(0,B - A);
		memo[0] = 0;
		memo[1] = 1;
		
		for(int i = 1; i <= B - A; i++){
			while(!proc[i].empty()){
				//printf("e%d\n",proc[i].back());
				root -> update(proc[i].back(),memo[proc[i].back()] + 2);
				proc[i].pop_back();
			}
			
			if(i == 1){
				int it2 = lower_bound(pre.begin(),pre.end(), lst[i + A] + pre[i]) - pre.begin();
				
			proc[it2 + 1].push_back(i);  
			}
			if(pre[i - 1] - lst[i + A] < 0){
				memo[i] = 1;
				continue;
			}
			
			int it1 = upper_bound(pre.begin(),pre.end(), pre[i - 1] - lst[i + A]) - pre.begin() - 1;
			
			memo[i] = max(memo[i],root -> query(0,it1));
			
			it1 = lower_bound(pre.begin(),pre.end(), lst[i + A] + pre[i]) - pre.begin();
			
			proc[it1 + 1].push_back(i);  
			
			//printf("%d %d\n",i,memo[i]);
		}
		
		printf("%d\n",memo[B - A]);
	}
	
	
}

컴파일 시 표준 에러 (stderr) 메시지

mizuyokan2.cpp: In function 'int main()':
mizuyokan2.cpp:52:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |         scanf(" %d",&N);
      |         ~~~~~^~~~~~~~~~
mizuyokan2.cpp:55:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |                 scanf(" %d",&lst[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~
mizuyokan2.cpp:60:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |         scanf(" %d",&Q);
      |         ~~~~~^~~~~~~~~~
mizuyokan2.cpp:69:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   69 |                 scanf(" %d",&X);
      |                 ~~~~~^~~~~~~~~~
mizuyokan2.cpp:70:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   70 |                 scanf(" %d",&Y);
      |                 ~~~~~^~~~~~~~~~
mizuyokan2.cpp:71:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   71 |                 scanf(" %d",&A);
      |                 ~~~~~^~~~~~~~~~
mizuyokan2.cpp:72:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   72 |                 scanf(" %d",&B);
      |                 ~~~~~^~~~~~~~~~

• Subtask 1: 0 / 6
• Subtask 2: 0 / 9
• Subtask 3: 0 / 13
• Subtask 4: 0 / 32
• Subtask 5: 0 / 29
• Subtask 6: 0 / 11