제출 #1163354

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1163354		LCJLY	Real Mountains (CCO23_day1problem2)	C++20	18 / 25	3515 ms	315688 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define int long long 
#define ld long double
#define show(x,y) cout << y << " " << #x << endl;
#define show2(x,y,i,j) cout << y << " " << #x << "  " << j << " " << #i << endl;
#define show3(x,y,i,j,p,q) cout << y << " " << #x << "  " << j << " " << #i << "  " << q << " " << #p << endl;
#define show4(x,y) for(auto it:y) cout << it << " "; cout << #x << endl;
typedef pair<int,int>pii;
typedef pair<pii,int>pi2;
mt19937_64 rng(chrono::system_clock::now().time_since_epoch().count());

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

struct node{
	int s,e,m;
	node *l,*r;
	int v;
	int v2;
	int lazyUpd;
	
	node(int ss, int ee):s(ss),e(ee),m((s+e)>>1),v(0),v2(1e15),lazyUpd(0){
		if(s!=e){
			l=new node(s,m);
			r=new node(m+1,e);
		}
	}
	
	void upd(int x, int y){
		if(s==e){
			v=y;
			return;
		}
		forceProp();
		if(x<=m) l->upd(x,y);
		else r->upd(x,y);
		v=combine(l->v,r->v);
	}
	
	int query(int x, int y){
		if(x<=s&&y>=e){
			return v;
		}
		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));
	}
	
	void self_add(int x){
		v2+=x;
		lazyUpd+=x;
	}
	
	void forceProp(){
		if(s==e) return;
		if(lazyUpd){
			l->self_add(lazyUpd);
			r->self_add(lazyUpd);
			lazyUpd=0;
		}
	}
	
	void rangeUpd(int x, int y, int c){
		if(x<=s&&y>=e){
			self_add(c);
			return;
		}
		forceProp();
		if(x<=m) l->rangeUpd(x,y,c);
		if(y>m) r->rangeUpd(x,y,c);
		v2=combine(l->v2,r->v2); 
	}
	
	int query2(int x, int y){
		if(x<=s&&y>=e){
			return v2;
		}
		forceProp();
		if(y<=m) return l->query2(x,y);
		if(x>m) return r->query2(x,y);
		return combine(l->query2(x,m),r->query2(m+1,y));
	}
};

const int mod=1e6+3;

void solve(){
	int n;
	cin >> n;
	int arr[n];
	node st(0,n+5);
	pii maxi={-1,-1};
	vector<int>dis;
	for(int x=0;x<n;x++){
		cin >> arr[x];
		st.upd(x,arr[x]);
		dis.push_back(arr[x]);
		maxi=max(maxi,{arr[x],x});
	}
	
	int target[n];
	int cur=0;
	for(int x=0;x<=maxi.second;x++){
		cur=max(cur,arr[x]);
		target[x]=cur;
	}
	
	cur=0;
	for(int x=n-1;x>=maxi.second;x--){
		cur=max(cur,arr[x]);
		target[x]=cur;
	}
	
	sort(dis.begin(),dis.end());
	dis.resize(unique(dis.begin(),dis.end())-dis.begin());
	
	vector<int>storage[n+5];
	vector<int>storage2[n+5];
	
	for(int x=0;x<n;x++){
		int a=lower_bound(dis.begin(),dis.end(),arr[x])-dis.begin();
		int b=lower_bound(dis.begin(),dis.end(),target[x])-dis.begin();
		
		storage[a].push_back(x);
		storage2[b].push_back(x);
	}
	
	vector<pii>pref;
	pref.push_back({arr[0],0});
	for(int x=1;x<n;x++){
		if(arr[x]<pref.back().first){
			st.rangeUpd(pref.back().second,x-1,pref.back().first);
			pref.push_back({arr[x],x});
		}
	}
	st.rangeUpd(pref.back().second,n-1,pref.back().first);
	
	vector<pii>suf;
	suf.push_back({arr[n-1],n-1});
	for(int x=n-1;x>=0;x--){
		if(arr[x]<suf.back().first){
			st.rangeUpd(x+1,suf.back().second,suf.back().first);
			suf.push_back({arr[x],x});
		}
	}
	st.rangeUpd(0,suf.back().second,suf.back().first);
	
	multiset<int>se;
	int counter=0;
	for(int x=0;x<n;x++){
		//pull from previous
		if(se.size()==1){
			int diff=dis[x]-dis[x-1];
			int index=*se.begin();
			int lft=st.query(0,index-1);
			int rgt=st.query(index+1,n-1);
			counter+=(lft+rgt)*diff;
			counter+=(dis[x]-1+dis[x-1])*diff/2*se.size();
			counter%=mod;
		}
		else if(se.size()==2){
			int diff=dis[x]-dis[x-1];
			int index=*se.begin();
			int index2=*prev(se.end());
			int lft=st.query(0,index-1);
			int a=st.query(index+1,n-1);
			int rgt=st.query(index2+1,n-1);
			int b=st.query(0,index2-1);
			counter+=(lft+rgt)*diff+min(a,b)*diff+(dis[x]+dis[x-1]+1)*diff/2;
			counter+=(dis[x]-1+dis[x-1])*diff/2*se.size();
			counter%=mod;
		}
		else if(se.size()>2){
			//int cost=0;
			//show4(se,se);
			//for(int y=0;y<n;y++){
				//cout << st.query2(y,y) << " ";
			//}
			//cout << " st\n";
			int diff=dis[x]-dis[x-1];
			int index=*se.begin();
			int index2=*prev(se.end());
			int lft=st.query(0,index-1);
			int a=st.query(index+1,n-1);
			int rgt=st.query(index2+1,n-1);
			int b=st.query(0,index2-1);
			
			int cost=(lft+rgt)*diff+min(a,b)*diff+(dis[x]+dis[x-1]+1)*diff/2;
			cost+=(se.size()-2)*(dis[x]+dis[x-1]+1)*diff;
			cost+=(dis[x]-1+dis[x-1])*diff/2*se.size();
			
			//int hold=(lft+rgt)*diff+(dis[x]+dis[x-1]+1)*diff;
			//hold+=(se.size()-3)*(dis[x]+dis[x-1]+1)*diff; //constant
			//hold+=(dis[x]-1+dis[x-1])*diff/2*se.size(); //constant
			//int take=st.query2(index+1,index2-1);
			//show(take,take);
			//hold+=take*diff;
			//show2(cost,cost,hold,hold);
			//cost=min(cost,hold);
			
			//int cost2=1e15;
			//auto it=se.begin();
			//while(it!=prev(se.end())){
				//int lft2=st.query(0,*it-1);
				//int rgt2=st.query(*it+1,n-1);
				//int hold=(lft+rgt)*diff+(dis[x]+dis[x-1]+1)*diff;
				//hold+=(se.size()-3)*(dis[x]+dis[x-1]+1)*diff;
				//hold+=(lft2+rgt2)*diff;
				//hold+=(dis[x]-1+dis[x-1])*diff/2*se.size();
				//cost2=min(cost2,hold);
				//it++;
			//}
			//show(cost2,cost2);
			
			counter+=cost;
			counter%=mod;
		}
		for(auto it:storage[x]){
			//st.upd(it,{1e15,-1e15});
			st.upd(it,1e15);
			st.rangeUpd(it,it,-1e15);
			se.insert(it);
		}
		for(auto it:storage2[x]){
			se.erase(se.find(it));
			//st.upd(it,{1e15,1e15});
			st.rangeUpd(it,it,1e15);
		}
		
		if(pref.back().first==dis[x]){
			st.rangeUpd(pref.back().second,n-1,-pref.back().first);
			pref.pop_back();
			if(!pref.empty()){
				st.rangeUpd(pref.back().second,n-1,pref.back().first);
			}
		}
		
		if(suf.back().first==dis[x]){
			st.rangeUpd(0,suf.back().second,-suf.back().first);
			suf.pop_back();
			if(!suf.empty()){
				st.rangeUpd(0,suf.back().second,suf.back().first);
			}
		}
		//show(counter,counter);
	}
	
	cout << counter;
}

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	//freopen("in.txt","r",stdin);
	//freopen("out.txt","w",stdout);
	int t=1;	
	//cin >> t;	
	while(t--){
		solve(); 
	}
}

• Subtask 1: 3 / 3
• Subtask 2: 3 / 3
• Subtask 3: 3 / 3
• Subtask 4: 0 / 3
• Subtask 5: 4 / 4
• Subtask 6: 5 / 5
• Subtask 7: 0 / 4