Submission #941079

#	Time	Username	Problem	Language	Result	Execution time	Memory
941079		dsyz	Stone Arranging 2 (JOI23_ho_t1)	C++17	100 / 100	248 ms	52924 KiB

Main

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define MAXN (1000005)
struct node {
	ll s,e,m,lazy,v;
	node *l, *r;
	node(ll _s,ll _e){
		s = _s;
		e = _e;
		m = (s + e) / 2;
		lazy = -1;
		v = 0;
		if(s != e){
			l = new node(s,m);
			r = new node(m + 1,e);
		}
	}
	void propo(){
		if(lazy == -1) return;
		v = (e-s+1) * lazy;
		if(s != e){
			l->lazy = lazy;
			r->lazy = lazy;
		}
		lazy = -1;
	}
	void update(ll x,ll y,ll nval){
		propo();
		if(s == x && e == y){
			lazy = nval;
			return;
		}else{
			if(x > m) r -> update(x,y,nval);
			else if(y <= m) l -> update(x,y,nval);
			else l -> update(x,m,nval), r -> update(m + 1,y,nval);
			l->propo(), r->propo();
			v = l->v + r->v;
		}
	}
	ll query(ll x){
		propo();
		if(s == e){
			return v;
		}else{
			if(x > m) return r -> query(x);
			else return l -> query(x);
		}
	}
} *root;
int main() {
	ios_base::sync_with_stdio(false);cin.tie(0);
	ll N;
	cin>>N;
	root = new node(0,N - 1);
	ll arr[N];
	for(ll i = 0;i < N;i++){
		cin>>arr[i];
	}
	map<ll,vector<ll> > val;
	for(ll i = 0;i < N;i++){
		while(!val[arr[i]].empty() && root -> query(val[arr[i]].back()) != arr[i]){
			val[arr[i]].pop_back();
		}
		ll Lb = i;
		if(!val[arr[i]].empty()) Lb = val[arr[i]].back();
		root -> update(Lb,i,arr[i]);
		val[arr[i]].push_back(i);
	}
	for(ll i = 0;i < N;i++){
		cout<<root -> query(i)<<'\n';
	}
}

• Subtask 1: 25 / 25
• Subtask 2: 35 / 35
• Subtask 3: 40 / 40