Submission #742559

#	Time	Username	Problem	Language	Result	Execution time	Memory
742559		LCJLY	Art Exhibition (JOI18_art)	C++14	100 / 100	792 ms	87040 KiB

art

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

#define int long long
typedef pair<int,int>pii;

inline int combine(int a, int b){
	return max(a,b);
}

const int defval=0;
#define lazyChange 1
#define setSentinel -1

struct node{
	int s,e,m;
	node *l, *r;
	int v;
	bool lset;
	int lazyUpd, lazySet;
	
	node(int ss, int ee):s(ss),e(ee),m((s+e)>>1),l(NULL),r(NULL),v(defval),lazyUpd(0),lazySet(setSentinel),lset(0){
	}
	
	inline void inst(){
		if(l==NULL)l=new node(s,m);
		if(r==NULL)r=new node(m+1,e);
	}
	
	void self_set(int x){
		lset=1;
		lazySet=x;
		v=lazyChange*x;
		lazyUpd=0;
	}
	
	void self_add(int x){
		if(lset){self_set(x+lazySet);return;}
		lazyUpd+=x;
		v+=x*lazyChange;
	}
	
	void forceProp(){
		if(s==e) return;
		if(lset){
			l->self_set(lazySet),r->self_set(lazySet);
			lset=lazySet=0;
		}
		if(lazyUpd!=0){
			l->self_add(lazyUpd),r->self_add(lazyUpd);
			lazyUpd=0;
		}
	}
	
	void rangeUpd(int first, int last, int c){
		if(first<=s&&last>=e){
			self_add(c);
			return;
		}
		inst();
		forceProp();
		if(first<=m)l->rangeUpd(first,last,c);
		if(last>m)r->rangeUpd(first,last,c);
		v=combine(l->v,r->v);
	}
	
	void rangeSet(int first, int last, int c){
		if(first<=s&&last>=e){
			self_set(c);
			return;
		}
		inst();
		forceProp();
		if(first<=m)l->rangeUpd(first,last,c);
		if(last>m)r->rangeUpd(first,last,c);
		v=combine(l->v,r->v);
	}
	
	int query(int x, int y){
		if(s==e){
			return v;
		}
		if(x<=s&&y>=e){
			forceProp(); return v;
		}
		inst();
		forceProp();
		if(y<=m) return l->query(x,y);
		if(x>m)return r->query(x,y);
		return combine(l->query(x,m),r->query(m+1,y));
	}
};

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n;
	cin >> n;
	
	pii arr[n+5];
	
	//size value
	for(int x=1;x<=n;x++){
		cin >> arr[x].first >> arr[x].second;
	}
	
	sort(arr+1,arr+n+1);
	
	node st(0,n+5);
	
	int counter=0;
	for(int x=1;x<=n;x++){
		counter+=arr[x].second;
		
		st.rangeUpd(x,x,counter-arr[x].first);
	}
	
	int best=0;
	for(int x=1;x<=n;x++){
		int mini=arr[x].first;
		int hold=st.query(x,n);
		best=max(best,hold+mini);
		st.rangeUpd(x,n,-arr[x].second);
	}
	
	cout << best;
	
}

Compilation message (stderr)

art.cpp: In constructor 'node::node(long long int, long long int)':
art.cpp:20:15: warning: 'node::lazySet' will be initialized after [-Wreorder]
   20 |  int lazyUpd, lazySet;
      |               ^~~~~~~
art.cpp:19:7: warning:   'bool node::lset' [-Wreorder]
   19 |  bool lset;
      |       ^~~~
art.cpp:22:2: warning:   when initialized here [-Wreorder]
   22 |  node(int ss, int ee):s(ss),e(ee),m((s+e)>>1),l(NULL),r(NULL),v(defval),lazyUpd(0),lazySet(setSentinel),lset(0){
      |  ^~~~
art.cpp: In member function 'void node::forceProp()':
art.cpp:47:16: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   47 |    lset=lazySet=0;
      |         ~~~~~~~^~

• Subtask 1: 10 / 10
• Subtask 2: 20 / 20
• Subtask 3: 20 / 20
• Subtask 4: 50 / 50