oj.uz

Submission #27108

# Submission time Handle Problem Language Result Execution time Memory
27108 2017-07-09T09:32:28 Z 서규호(#1119) Editor (BOI15_edi) C++14
100 / 100
 1008 ms 236388 KB 
#include <bits/stdc++.h>

#define lld long long
#define pii pair<int,int>
#define pb push_back
#define next nextt
#define Inf 1000000000
#define Linf 1000000000000000000LL
#define Mod 1000000007

using namespace std;

int N;
int a[300002];
int ans[300002];

struct Node{
	int x;
	Node *left,*right;
	Node(){
		x = 1;
		left = right = NULL;
	}
};
Node *root[300002];

void dfs(Node *now,int l,int r){
	if(l == r) return;
	now->left = new Node();
	now->right = new Node();
	int mid = (l+r)>>1;
	dfs(now->left,l,mid);
	dfs(now->right,mid+1,r);
}
void update(Node *now,Node *par,int l,int r,int where,int value){
	if(l == r){
		now->x = value;
		return;
	}
	int mid = (l+r)>>1;
	if(where <= mid){
		now->right = par->right;
		now->left = new Node();
		update(now->left,par->left,l,mid,where,value);
	}else{
		now->left = par->left;
		now->right= new Node();
		update(now->right,par->right,mid+1,r,where,value);
	}
	now->x = max(now->left->x,now->right->x);
}

int finding(Node *now,int l,int r,int value){
	if(r < value) return 1;
	if(value <= l) return now->x;
	int mid = (l+r)>>1;
	return max(finding(now->left,l,mid,value),finding(now->right,mid+1,r,value));
}

int main(){
	scanf("%d",&N);
	root[0] = new Node();
	dfs(root[0],-N,N);
	for(int i=1; i<=N; i++){
		scanf("%d",&a[i]);
		root[i] = new Node();
		if(a[i] > 0){
			ans[i] = a[i];
			update(root[i],root[i-1],-N,N,a[i],i);
		}else{
			int tmp;
			tmp = finding(root[i-1],-N,N,a[i]+1)-1;
			ans[i] = ans[tmp];
			update(root[i],root[tmp],-N,N,a[i],i);
		}
		printf("%d\n",ans[i]);
	}

	return 0;
}

Compilation message

edi.cpp: In function 'int main()':
edi.cpp:61:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&N);
                ^
edi.cpp:65:20: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&a[i]);
                    ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6708 KB Output is correct
2 Correct 6 ms 9612 KB Output is correct
3 Correct 0 ms 6708 KB Output is correct
4 Correct 0 ms 6708 KB Output is correct
5 Correct 6 ms 9612 KB Output is correct
6 Correct 0 ms 6708 KB Output is correct
7 Correct 3 ms 9612 KB Output is correct
8 Correct 0 ms 6708 KB Output is correct
9 Correct 9 ms 9612 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 666 ms 232956 KB Output is correct
2 Correct 496 ms 232956 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 303 ms 115740 KB Output is correct
2 Correct 313 ms 139104 KB Output is correct
3 Correct 386 ms 186096 KB Output is correct
4 Correct 566 ms 232956 KB Output is correct
5 Correct 936 ms 234144 KB Output is correct
6 Correct 439 ms 236388 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 6708 KB Output is correct
2 Correct 6 ms 9612 KB Output is correct
3 Correct 0 ms 6708 KB Output is correct
4 Correct 0 ms 6708 KB Output is correct
5 Correct 6 ms 9612 KB Output is correct
6 Correct 0 ms 6708 KB Output is correct
7 Correct 3 ms 9612 KB Output is correct
8 Correct 0 ms 6708 KB Output is correct
9 Correct 9 ms 9612 KB Output is correct
10 Correct 666 ms 232956 KB Output is correct
11 Correct 496 ms 232956 KB Output is correct
12 Correct 303 ms 115740 KB Output is correct
13 Correct 313 ms 139104 KB Output is correct
14 Correct 386 ms 186096 KB Output is correct
15 Correct 566 ms 232956 KB Output is correct
16 Correct 936 ms 234144 KB Output is correct
17 Correct 439 ms 236388 KB Output is correct
18 Correct 659 ms 234144 KB Output is correct
19 Correct 569 ms 234144 KB Output is correct
20 Correct 503 ms 234144 KB Output is correct
21 Correct 683 ms 232956 KB Output is correct
22 Correct 1008 ms 234144 KB Output is correct