oj.uz

Submission #754975

# Submission time Handle Problem Language Result Execution time Memory
754975 2023-06-09T07:52:21 Z ByeWorld Editor (BOI15_edi) C++14
0 / 100
 390 ms 333240 KB 
#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 >> subtask;
	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
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 28.0

# Verdict Execution time Memory Grader output
1 Runtime error 390 ms 333240 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 37.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -