# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
344941 | nicolaalexandra | 입자 가속기 (IZhO11_collider) | C++14 | 342 ms | 61676 KiB |
이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define DIM 1000010
#define INF 2000000000
using namespace std;
struct treap{
int val,priority,nr;
treap *left, *right;
treap (int val, int priority, int nr, treap *left, treap *right){
this->val = val;
this->priority = priority;
this->nr = nr;
this->left = left;
this->right = right;
}
};
treap *rad, *nil;
int n,q,x,y,poz,i;
char s[DIM];
int get_random(){
return rand() % (INF-1) + 1;
}
treap* update (treap *rad){
if (rad == nil)
rad->val = rad->nr = 0;
else rad->nr = rad->left->nr + rad->right->nr + 1;
return rad;
}
/*pair <treap*, treap*> split (treap *rad, int poz){
rad = update (rad);
pair <treap*, treap*> ans;
if (rad == nil)
return make_pair (nil,nil);
if (rad->left->nr + 1 > poz){
ans = split (rad->left,poz);
rad->left = ans.second;
ans.second = rad;
} else {
ans = split (rad->right,poz - rad->left->nr - 1);
rad->right = ans.first;
ans.first = rad;
}
rad = update (rad);
return ans;
}
treap* join (treap *rad1, treap *rad2){
if (rad1 == nil)
return rad2;
if (rad2 == nil)
return rad1;
rad1 = update (rad1), rad2 = update (rad2);
if (rad1->priority <= rad2->priority){
rad2->left = join (rad1,rad2->left);
rad2 = update (rad2);
return rad2;
} else {
rad1->right = join (rad1->right,rad2);
rad1 = update (rad1);
return rad1;
}
return nil;
}
treap* _insert (treap *rad, int poz, int val, int priority){
if (rad == nil){
rad = new treap (val,priority,1,nil,nil);
rad = update (rad);
return rad;
}
pair<treap*, treap*> aux = split (rad,poz-1);
rad = new treap (val,priority,1,aux.first,aux.second);
rad = update(rad);
return rad;
}
int get_elem (treap *&rad, int poz){
rad = update (rad);
if (rad->left->nr + 1 == poz)
return rad->val;
else {
if (rad->left->nr + 1 > poz)
return get_elem (rad->left,poz);
else return get_elem (rad->right,poz-rad->left->nr-1);
}
}
treap* _delete (treap *rad, int x, int y){
pair <treap*,treap*> aux = split (rad,y);
pair <treap*,treap*> aux2 = split (aux.first,x-1);
rad = join (aux2.first, aux.second);
rad = update (rad);
return rad;
}*/
pair <treap*, treap*> split (treap *rad, int poz){
rad = update (rad);
pair <treap*, treap*> ans;
if (rad == nil)
return make_pair (nil,nil);
if (rad->left->nr >= poz){
ans = split (rad->left,poz);
rad->left = ans.second;
ans.second = rad;
} else {
ans = split (rad->right,poz-rad->left->nr-1);
rad->right = ans.first;
ans.first = rad;
}
rad = update (rad);
return ans;
}
treap* join (treap *rad1, treap *rad2){
if (rad1 == nil)
return rad2;
if (rad2 == nil)
return rad1;
rad1 = update (rad1), rad2 = update (rad2);
if (rad1->priority > rad2->priority){
rad1->right = join (rad1->right,rad2);
rad1 = update (rad1);
return rad1;
} else {
rad2->left = join (rad1,rad2->left);
rad2 = update (rad2);
return rad2;
}
return nil;
}
treap* _insert (treap *rad, int poz, int val, int priority){
if (rad == nil){
rad = new treap (val,priority,1,nil,nil);
rad = update (rad);
return rad;
}
pair<treap*, treap*> aux = split (rad,poz-1);
rad = new treap (val,priority,1,aux.first,aux.second);
rad = update(rad);
return rad;
}
treap *_delete (treap *rad, int poz){
pair <treap*, treap*> aux = split (rad,poz);
pair <treap*, treap*> aux2 = split (aux.first,poz-1);
rad = join (aux2.first,aux.second);
rad = update (rad);
return rad;
}
int access (treap *&rad, int poz){
rad = update (rad);
if (rad->left->nr + 1 == poz)
return rad->val;
else {
if (rad->left->nr + 1 > poz)
return access (rad->left,poz);
else return access (rad->right,poz-rad->left->nr-1);
}
}
int main (){
//ifstream cin ("date.in");
//ofstream cout ("date.out");
rad = nil = new treap (0,0,0,NULL,NULL);
cin>>n>>q>>s+1;
for (i=1;i<=n;i++){
int val = s[i] - 'x' + 1;
rad = _insert (rad,i,val,get_random());
}
for (;q--;){
char tip; cin>>tip;
if (tip == 'a'){
cin>>x>>y;
int val = access (rad,x);
rad = _delete(rad,x);
rad = _insert (rad,y,val,get_random());
} else {
cin>>poz;
cout<<char('x' + access(rad,poz) - 1)<<"\n";
}
}
return 0;
}
컴파일 시 표준 에러 (stderr) 메시지
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |