Submission #754977

#	Time	Username	Problem	Language	Result	Execution time	Memory
754977		ByeWorld	Editor (BOI15_edi)	C++14	100 / 100	556 ms	331764 KiB

edi

#include <bits/stdc++.h>
#pragma GCC optimize("O1")
//#define int long long
#define ll long long
#define fi first
#define se second
#define pb push_back
using namespace std;
typedef pair<int,int> pii;
typedef pair<int,pii> ipii;
const int MAXN = 3e5+10;

struct node{//segtree RMQ
	int val = 0; int l, r;
	node *le, *ri;
	void bd(int l2, int r2){
		l = l2; r = r2;
		if(l==r) return;
	}
	int que(int x, int y){
		if(x<=l && r<=y) return val;
		if(r<x || y<l) return 0;
		if(le == NULL){
			le = new node(); le->bd(l, (l+r)/2);
		}
		if(ri == NULL){
			ri = new node(); ri->bd((l+r)/2+1, r);
		}
		return max(le->que(x, y), ri->que(x, y));
	}
	node *upd(int x, int p){
		if(r<x || x<l) return this;
		if(le == NULL){
			le = new node(); le->bd(l, (l+r)/2);
		}
		if(ri == NULL){
			ri = new node(); ri->bd((l+r)/2+1, r);
		}
		//mengandung x
		node *ret; ret = new node();
		*ret = *this;

		if(l==r){
			ret->val = p;
			return ret;
		}

		ret->le = ret->le->upd(x, p);
		ret->ri = ret->ri->upd(x, p);
		ret->val = max(ret->le->val, ret->ri->val);
		return ret;
	}
};

node *A[MAXN];
int n, subtask;
int t[MAXN];

signed main(){
	ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	cin >> n;
	A[0] = new node(); 
	A[0]->bd(0, MAXN-10);

	for(int i=1; i<=n; i++){
		A[i] = new node();

		cin >> t[i];
		if(t[i] > 0){
			*A[i] = *A[i-1];
			A[i] = A[i]->upd(0, i);
			//cout << i-1 << ' ' << A[i-1]->que(0, 0) << "que\n";
		} else {
			int idx = A[i-1]->que(0, (-t[i])-1); 
			*A[i] = *A[idx-1];
			A[i] = A[i]->upd((-t[i]), i);
		}
		cout << t[A[i]->que(0, 0)] << '\n';
		//cout << t[A[i]->que(0, 0)] << ' ' << A[i]->que(0, 0) <<'p'<< '\n';
		/*for(int j=i; j>=1; j--){
			cout << A[j]->que(0, 0) << ' ' << j << '\n';
		}*/
	}
}

• Subtask 1: 20 / 20
• Subtask 2: 15 / 15
• Subtask 3: 28 / 28
• Subtask 4: 37 / 37