Submission #1149538

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149538		henriess	Stone Arranging 2 (JOI23_ho_t1)	C++20	25 / 100	2095 ms	26948 KiB

Main

#include <bits/stdc++.h>
using namespace std;
//segment tree?? 
vector<long long>A;
struct node{
	node *left,*right;
	long long S,E,M;
	long long val;
	long long lazy;
	node (long long s,long long e):S(s), E(e){
		val = 0;
		left = nullptr;
		right = nullptr;
		lazy = 0;
	}
	void prop(){
		if (S == E){
			return;
		}
		M = (S + E) / 2;
		if (left == nullptr){
			left = new node(S,M);
			right = new node(M+1,E);
		}
		if (lazy != 0){
			left->val = lazy;
			right->val = lazy;
			right->lazy = lazy;
			left->lazy = lazy;
			lazy = 0;
		}
	}
	long long qry(long long l,long long r){
		if (l > E || r < S){
			return 0;
		}
		else if (l <= S && r >= E){
			return val;
		}
		prop();
		return left->qry(l,r) + right->qry(l,r);
	}
	void upd(long long l,long long r,long long v){
		if (l > E || r < S){
			return;
		}
		if (l <= S && E <= r){
			val = v;
			lazy = v;
			return;
		}
		prop();
		left->upd(l,r,v);
		right->upd(l,r,v);
		val = left->val + right->val;
	}
	long long find(long long x){
		if (S == E){
			if (val == x){
				return S;
			}
			else{
				return -1;
			}
		}
		prop();
		long long ret = right->find(x);
		if (ret != -1){
			return ret;
		}
		long long ret2 = left->find(x);
		return ret2;
	}
			
}*segtree;


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    long long n;cin >> n;
    A.resize(n);
    segtree = new node(0,n-1);
   
    for(int i = 0;i<n;i++){
		cin >> A[i] ;
		
	}
	
	//put the stones in order
	
	
	for(int i = 0;i<n;i++){
		if (i == 0){
			segtree->upd(i,i,A[i]);
			continue;
		}
		long long index = segtree->find(A[i]);

		if (index != -1){
			segtree->upd(index,i,A[i]);
		}
		segtree->upd(i,i,A[i]);
	
	}
	for(int i = 0;i<n;i++){
		cout << segtree->qry(i,i) << '\n';
	}
}

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