Submission #1686820
Source Code Expand
#include<bits/stdc++.h>
using namespace std;
using Int = long long;
//BEGIN CUT HERE
template<typename T>
struct AVL{
struct node{
T key;
int size,height;
node *child[2];
node (const T &key):key(key),size(1),height(1){
child[0]=child[1]=0;
}
} *root;
typedef node *pointer;
AVL(){root=NULL;}
pointer find(T key){
return find(root,key);
}
node *find(node *t,const T key){
if(t==NULL) return NULL;
if(key==(t->key)) return t;
else if(key<(t->key)) return find(t->child[0],key);
else return find(t->child[1],key);
}
void insert(const T key){
root=insert(root,new node(key));
}
node *insert(node *t,node *x){
if(t==NULL) return x;
if((x->key)<=(t->key)) t->child[0]=insert(t->child[0],x);
else t->child[1]=insert(t->child[1],x);
t->size+=1;
return balance(t);
}
void erase(const T key){
int t=key;
if(find(t)==NULL) return;
root=erase(root,key);
}
node *erase(node *t,const int x){
if(t==NULL) return NULL;
if(x==(t->key)){
return move_down(t->child[0],t->child[1]);
}else{
if(x<(t->key)) t->child[0]=erase(t->child[0],x);
else t->child[1]=erase(t->child[1],x);
t->size-=1;
return balance(t);
}
}
node *move_down(node *t,node *rhs){
if(t==NULL) return rhs;
t->child[1]=move_down(t->child[1],rhs);
return balance(t);
}
int sz(node *t){
if(t!=NULL) return t->size;
return 0;
}
int ht(node *t){
if(t!=NULL) return t->height;
return 0;
}
node *rotate(node *t,int l,int r){
node *s=t->child[r];
t->child[r]=s->child[l];
s->child[l]=balance(t);
if(t!=NULL) t->size=sz(t->child[0])+sz(t->child[1])+1;
if(s!=NULL) s->size=sz(s->child[0])+sz(s->child[1])+1;
return balance(s);
}
node *balance(node *t){
for(int i=0;i<2;i++){
if(ht(t->child[!i])-ht(t->child[i])<-1){
if(ht(t->child[i]->child[!i])-ht(t->child[i]->child[i])>0)
t->child[i]=rotate(t->child[i],i,!i);
return rotate(t,!i,i);
}
}
if(t!=NULL) t->height=max(ht(t->child[0]),ht(t->child[1]))+1;
if(t!=NULL) t->size=sz(t->child[0])+sz(t->child[1])+1;
return t;
}
pointer rank(int k){
return rank(root,k);
}
pointer rank(node *t,int k){
if(t==NULL) return NULL;
int m=sz(t->child[0]);
if(k<m) return rank(t->child[0],k);
if(k==m) return t;
if(k>m) return rank(t->child[1],k-m-1);
}
int index(T key){
if(find(key)==NULL) return -1;
return index(root,key);
}
int index(node *t,T key){
if(key==(t->key)) return sz(t->child[0]);
if(key<(t->key)) return index(t->child[0],key);
else return sz(t)-sz(t->child[1])+index(t->child[1],key);
}
};
//END CUT HERE
signed main(){
int n,k;
cin>>n>>k;
int x[n];
for(int i=0;i<n;i++) cin>>x[i];
map<int,int> m;
for(int i=0;i<n;i++) m[x[i]]=i+1;
AVL<Int> avl;
for(int i=0;i<k-1;i++) avl.insert(x[i]);
for(int i=k-1;i<n;i++){
avl.insert(x[i]);
Int key=avl.rank(k-1)->key;
cout<<m[key]<<endl;
assert(avl.index(key)==k-1);
}
return 0;
}
/*
verified on 2017/02/24
http://arc028.contest.atcoder.jp/tasks/arc028_2
http://arc033.contest.atcoder.jp/tasks/arc033_3
*/
Submission Info
Submission Time |
|
Task |
B - 特別賞 |
User |
beet |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
3335 Byte |
Status |
AC |
Exec Time |
285 ms |
Memory |
10496 KB |
Judge Result
Set Name |
Sample |
Subtask1 |
Subtask2 |
Score / Max Score |
0 / 0 |
40 / 40 |
60 / 60 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
sample_01.txt, sample_02.txt |
Subtask1 |
sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt |
Subtask2 |
sample_01.txt, sample_02.txt, subtask1_01.txt, subtask1_02.txt, subtask1_03.txt, subtask1_04.txt, subtask1_05.txt, subtask1_06.txt, subtask1_07.txt, subtask1_08.txt, subtask1_09.txt, subtask1_10.txt, subtask1_11.txt, subtask2_01.txt, subtask2_02.txt, subtask2_03.txt, subtask2_04.txt, subtask2_05.txt, subtask2_06.txt, subtask2_07.txt, subtask2_08.txt, subtask2_09.txt |
Case Name |
Status |
Exec Time |
Memory |
sample_01.txt |
AC |
1 ms |
256 KB |
sample_02.txt |
AC |
1 ms |
256 KB |
subtask1_01.txt |
AC |
1 ms |
256 KB |
subtask1_02.txt |
AC |
1 ms |
256 KB |
subtask1_03.txt |
AC |
1 ms |
256 KB |
subtask1_04.txt |
AC |
1 ms |
256 KB |
subtask1_05.txt |
AC |
3 ms |
384 KB |
subtask1_06.txt |
AC |
4 ms |
384 KB |
subtask1_07.txt |
AC |
2 ms |
384 KB |
subtask1_08.txt |
AC |
3 ms |
384 KB |
subtask1_09.txt |
AC |
3 ms |
384 KB |
subtask1_10.txt |
AC |
3 ms |
384 KB |
subtask1_11.txt |
AC |
3 ms |
384 KB |
subtask2_01.txt |
AC |
33 ms |
1792 KB |
subtask2_02.txt |
AC |
3 ms |
384 KB |
subtask2_03.txt |
AC |
225 ms |
10368 KB |
subtask2_04.txt |
AC |
285 ms |
10496 KB |
subtask2_05.txt |
AC |
97 ms |
9984 KB |
subtask2_06.txt |
AC |
165 ms |
10240 KB |
subtask2_07.txt |
AC |
194 ms |
10368 KB |
subtask2_08.txt |
AC |
173 ms |
10368 KB |
subtask2_09.txt |
AC |
183 ms |
10368 KB |