Submission #1210700

#	Time	Username	Problem	Language	Result	Execution time	Memory
1210700		salmon	Worst Reporter 4 (JOI21_worst_reporter4)	C++20	79 / 100	517 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;
vector<int> de;

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;
		else if(n -> l != NULL) l -> merge(n -> l);
		
		if(r == NULL) r = n -> r;
		else if(n -> r != NULL) r -> merge(n -> r);
	}
	
	long long int query(int i){
		if(i <= m){
			if(l == NULL) return lazy;
			else return lazy + l -> query(i);
		}
		else{
			if(r == NULL) return lazy;
			else return lazy + r -> query(i);
		}
	}
	
	int queryin(long long int i){
		if(s == e){
			return s;
		}
		
		if(l != NULL && l -> v >= i - lazy){
			return l -> queryin(i - lazy);
		}
		else{
			if(r == NULL) return s;
			return r -> queryin(i - lazy);
		}
	}	
	
	void update(int k){
		lazy += k;
		v += k;
	}
	
	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){
			if(l == NULL) l = new node(s,m);
			l -> flapdate(S,E,k - lazy);
		}
		if(m < E){
			if(r == NULL) r = new node(m + 1, e);
			r -> flapdate(S,E,k - lazy);
		}
		
		if(r == NULL) v = lazy;
		else 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 it = lower_bound(de.begin(),de.end(),lst[i]) - de.begin();
	
	int pos = n -> queryin(n -> query(it) - cost[i]);
	
	n -> flapdate(pos,it,n -> query(it) - cost[i]);
	n -> update(cost[i]);
	//printf("%d\n",i);
	return n;
}

int main(){
	
	scanf(" %d",&N);
	
	de.push_back(0);
	
	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);
		de.push_back(lst[i]);
	}
	
	sort(de.begin(),de.end());
	de.resize(unique(de.begin(),de.end()) - de.begin());
	bound = de.size();
	
	printf("%lld\n",solve(1) -> query(0));
	
}

Compilation message (stderr)

worst_reporter2.cpp: In function 'int main()':
worst_reporter2.cpp:122:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  122 |         scanf(" %d",&N);
      |         ~~~~~^~~~~~~~~~
worst_reporter2.cpp:127:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  127 |                 scanf(" %d",&parent[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~~~~
worst_reporter2.cpp:128:22: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
  128 |                 scanf(" %d",&lst[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~
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",&cost[i]);
      |                 ~~~~~^~~~~~~~~~~~~~~~

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