# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
27108 |
2017-07-09T09:32:28 Z |
서규호(#1119) |
Editor (BOI15_edi) |
C++14 |
|
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]);
^
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
666 ms |
232956 KB |
Output is correct |
2 |
Correct |
496 ms |
232956 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
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 |
# |
결과 |
실행 시간 |
메모리 |
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 |