Submission #1210689

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210689		salmon	Worst Reporter 4 (JOI21_worst_reporter4)	C++20	14 / 100	587 ms	589824 KiB

worst_reporter2

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

int N;
vector<int> children[200100];
int parent[200100];
int sise[200100];
int lst[200100];
int cost[200100];
int bound = 1.1e9;

struct node{
	
	int s,e,m;
	node *l,*r;
	long long int lazy;
	long long int v;
	
	node(int S, int E){
		s = S;
		e = E;
		m = (s + e)/2;
		
		lazy = 0;
		v = 0;
		
		l = NULL;
		r = NULL;
	}
	
	void merge(node* n){
		v += n -> v;
		lazy += n -> lazy;
		
		if(l == NULL){
			l = n -> l;
			r = n -> r;
		}
		else if(n -> l != NULL){
			l -> merge(n -> l);
			r -> merge(n -> r);
		}
	}
	
	long long int query(int i){
		if(l == NULL) return lazy;
		
		if(i <= m) return lazy + l -> query(i);
		else return lazy + r -> query(i);
	}
	
	int queryin(long long int i){
		if(s == e){
			return s;
		}
		
		if(l == NULL) return s;
		
		if(l -> v >= i - lazy){
			return l -> queryin(i - lazy);
		}
		else{
			return r -> queryin(i - lazy);
		}
	}	
	
	void update(int S, int E, int k){
		if(S <= s && e <= E){
			lazy += k;
			v += k;
			return;
		}

		if(l == NULL){
			l = new node(s,m);
			r = new node(m + 1, e);
		}
		
			
		if(S <= m) l -> update(S,E,k);
		if(m < E) r -> update(S,E,k);
		
		v = max(l -> v, r -> v) + lazy;
	}
	
	void flapdate(int S, int E, long long int k){
		if(S <= s && e <= E){
			l = NULL;
			r = NULL;
			v = k;
			lazy = k;
			return;
		}
		
		if(l == NULL){
			l = new node(s,m);
			r = new node(m + 1, e);
		}
			
		if(S <= m) l -> flapdate(S,E,k - lazy);
		if(m < E) r -> flapdate(S,E,k - lazy);
		
		v = max(l -> v, r -> v) + lazy;
	}
	
};

node* solve(int i){// printf("%d\n",i);
	node* n = new node(0,bound);
	
	for(int j : children[i]){
		if(j == i) continue;
		n -> merge(solve(j));
	}
	
	int pos = n -> queryin(n -> query(lst[i]) - cost[i]);
	
	n -> flapdate(pos,lst[i],n -> query(lst[i]) - cost[i]);
	n -> update(0,bound,cost[i]);
	//printf("%d\n",i);
	return n;
}

int main(){
	
	scanf(" %d",&N);
	
	for(int i = 1; i <= N; i++){
		scanf(" %d",&parent[i]);
		scanf(" %d",&lst[i]); 
		scanf(" %d",&cost[i]);
	
		children[parent[i]].push_back(i);
	}
	
	printf("%lld\n",solve(1) -> query(1));
	
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:126:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  126 |         scanf(" %d",&N);
      |         ~~~~~^~~~~~~~~~
worst_reporter2.cpp:129:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  129 |                 scanf(" %d",&parent[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~
worst_reporter2.cpp:130:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  130 |                 scanf(" %d",&lst[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~
worst_reporter2.cpp:131:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  131 |                 scanf(" %d",&cost[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 14 / 14
• Subtask 2: 0 / 65
• Subtask 3: 0 / 21