Submission #1215553

#	Time	Username	Problem	Language	Result	Execution time	Memory
1215553		salmon	Fish 2 (JOI22_fish2)	C++20	13 / 100	4094 ms	13892 KiB

fish2

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

int N;
int Q;
int lst[100100];
int inf = 1.1e9;

struct node{
		
	int s, e, m;
	pair<int,int> v;
	long long int sum;
	node *l, *r;
	
	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);
			v = max(l -> v, r -> v);
			sum = l -> sum + r -> sum;
		}
		else{
			v = {lst[s],s};
			sum = lst[s];
		}
	}
	
	pair<int,int> query(int S, int E){
		if(S <= s && e <= E) return v;
		
		pair<int,int> ii = {0,-1};
		
		if(S <= m) ii = max(ii, l -> query(S,E));
		if(m < E) ii = max(ii, r -> query(S,E));
		
		return ii;
	}
	
	long long int querys(int S, int E){
		if(S <= s && e <= E){
			return sum;
		}
		
		long long int V = 0;
		
		if(S <= m) V += l -> querys(S,E);
		if(m < E) V += r -> querys(S,E);
		
		return V;
	}
	
	void update(int i, int k){
		if(s == e){
			v = {k,i};
			sum = k;
			return;
		}
		
		if(i <= m) l -> update(i,k);
		else r -> update(i,k);
		
		v = max(l -> v, r -> v);
		sum = l -> sum + r -> sum;
	}
	
}*root;

int decomp(int S, int E, int req){
	if(root -> querys(S,E) < req) return 0;
	
	int ans = 1;
	pair<int,int> ii = root -> query(S,E);
	int it = ii.second;
	
	if(it != S){
		ans += decomp(S,it-1,ii.first);
	}
	if(it != E){
		ans += decomp(it + 1, E, ii.first);
	}
	return ans;
	
}

int main(){
	
	scanf(" %d",&N);
	
	for(int i = 1; i <= N; i++){
		scanf(" %d",&lst[i]);
	}
	
	scanf(" %d",&Q);
	
	root = new node(1,N);
	
	for(int i = 0; i < Q; i++){
		int T;
		
		scanf(" %d",&T);
		
		if(T == 1){
			int X, Y;
			
			scanf(" %d",&X);
			scanf(" %d",&Y);
			
			root -> update(X,Y);
		}
		else{
			int L, R;
			
			scanf(" %d",&L);
			scanf(" %d",&R);
			
			printf("%d\n",decomp(L,R,0));
		}
	}
}

Compilation message (stderr)

fish2.cpp: In function 'int main()':
fish2.cpp:92:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |         scanf(" %d",&N);
      |         ~~~~~^~~~~~~~~~
fish2.cpp:95:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   95 |                 scanf(" %d",&lst[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~
fish2.cpp:98:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   98 |         scanf(" %d",&Q);
      |         ~~~~~^~~~~~~~~~
fish2.cpp:105:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  105 |                 scanf(" %d",&T);
      |                 ~~~~~^~~~~~~~~~
fish2.cpp:110:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  110 |                         scanf(" %d",&X);
      |                         ~~~~~^~~~~~~~~~
fish2.cpp:111:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  111 |                         scanf(" %d",&Y);
      |                         ~~~~~^~~~~~~~~~
fish2.cpp:118:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  118 |                         scanf(" %d",&L);
      |                         ~~~~~^~~~~~~~~~
fish2.cpp:119:30: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  119 |                         scanf(" %d",&R);
      |                         ~~~~~^~~~~~~~~~

• Subtask 1: 5 / 5
• Subtask 2: 8 / 8
• Subtask 3: 0 / 12
• Subtask 4: 0 / 23
• Subtask 5: 0 / 35
• Subtask 6: 0 / 17