結果
問題 | No.123 カードシャッフル |
ユーザー |
![]() |
提出日時 | 2015-01-11 23:26:58 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 49 ms / 5,000 ms |
コード長 | 7,018 bytes |
コンパイル時間 | 1,211 ms |
コンパイル使用メモリ | 94,228 KB |
実行使用メモリ | 6,944 KB |
最終ジャッジ日時 | 2024-06-13 04:10:23 |
合計ジャッジ時間 | 1,974 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 4 |
other | AC * 10 |
ソースコード
#include <iostream>#include <vector>#include <cstdio>#include <sstream>#include <map>#include <string>#include <algorithm>#include <queue>#include <cmath>using namespace std;template<class Type>class Treap{public:static const Type MIN_VAL = -100000000;static const Type MAX_VAL = +100000000;class Node{public:Type value;unsigned int priority;Node* left;Node* right;int sub_tree_size;//sub tree + posType sub_tree_sum;Type sub_tree_min;Type sub_tree_max;//reversed flagbool is_reversed;//range added flagbool is_range_added;int range_added_val;Node(Type val, unsigned int pri) :value(val),priority(pri),sub_tree_size(1),sub_tree_sum(val),sub_tree_min(val),sub_tree_max(val),left((Node*)NULL),right((Node*)NULL),is_reversed(false),is_range_added(false),range_added_val(0){}};Node* root;Treap(){root = (Node*)NULL;}int size(Node* t){if(t!=NULL) return t->sub_tree_size;else return 0;}Type sum(Node* t){if(t!=NULL) return t->sub_tree_sum;else return 0;}Type get_min(Node* t){if(t!=NULL) return t->sub_tree_min;else return MAX_VAL;}Type get_max(Node* t){if(t!=NULL) return t->sub_tree_max;else return MIN_VAL;}void push_reverse(Node* t){if(t == NULL) return;//node is reversedif(t->is_reversed == true){swap(t->left, t->right);if(t->left) t->left->is_reversed ^= true;if(t->right) t->right->is_reversed ^= true;t->is_reversed = false;}}void push_range_add(Node* t){if(t == NULL) return;//addedif(t->is_range_added == true){t->value += t->range_added_val;if(t->left){t->left->is_range_added = true;t->left->range_added_val += t->range_added_val;}if(t->right){t->right->is_range_added = true;t->right->range_added_val += t->range_added_val;}t->is_range_added = false;t->range_added_val = 0;}}void push(Node* t){//push_reverse(t);//push_range_add(t);}void reverse(Node* t){if(t == NULL) return;t->is_reversed ^= true;}void add(Node* t, Type v){if(t == NULL) return;t->is_range_added = true;t->range_added_val += v;}Node* update(Node* t){t->sub_tree_size = size( t->left ) + size( t->right ) + 1;push(t);t->sub_tree_sum = sum( t->left ) + sum( t->right ) + t->value;t->sub_tree_max = max( max( get_max( t->left ), get_max( t->right ) ), t->value );t->sub_tree_min = min( min( get_min( t->left ), get_min( t->right ) ), t->value );return t;}Node* merge(Node *l, Node *r){if(l==NULL) return r;if(r==NULL) return l;push(r);push(l);//left sub-tree has higher priorityif( l->priority > r->priority){l->right = merge(l->right, r);return update(l);}else{ // right sub-tree has higher priorityr->left = merge(l, r->left);return update(r);}}//split (( [0,k), [k,n) ]]pair<Node*, Node*> split(Node* t, int k){if(t == NULL) return make_pair((Node*)NULL, (Node*)NULL);push(t);if(k <= size(t->left)){pair<Node*, Node*> s = split(t->left, k);t->left = s.second;return make_pair(s.first, update(t) );}else{pair<Node*, Node*> s = split(t->right, k - size(t->left) -1 );t->right = s.first;return make_pair(update(t), s.second);}}Node* insert(Node* t, int k, Type val, unsigned int pri){pair<Node*, Node*> s = split(t, k);t = merge(s.first, new Node(val, pri));t = merge(t, s.second);return update(t);}Node* erase(Node* t, int k){//[0,k],[k+1,n-1]pair<Node*, Node*> s1 = split(t,k+1);//[0,k-1],[k,k]pair<Node*, Node*> s2 = split(s1.first, k);t = merge(s2.first, s1.second);return update(t);}//return k th nodeNode* find(Node* t, int k){push(t);int c = size(t->left);if(k<c) return find( t->left, k);if(k>c) return find( t->right, k-c-1);return t;}void insert(int k, Type val){root = insert(root, k, val, rand());}void erase(int k){root = erase(root, k);}Node* find(int k){return find(root, k);}//split at pos[i]//return root nodes begin with [ 0, pos[0], pos[1], ... , pos[n-1] ]vector<Node*> split_at(Node* t, const vector<int> &pos){vector<Node*> ret(pos.size()+1);for(int i=pos.size()-1; i>=0; i--){pair<Node*, Node*> p = split(t, pos[i]);ret[i+1] = p.second;t = p.first;}ret[0] = t;return ret;}//merge nodes in vector<Node*> vNode* merge_vec(const vector<Node*> &v){Node* r = v[0];for(int i=1; i<v.size(); i++){r = merge(r, v[i]);}return r;}//[l,r) <-> [x,y)void swap_range(int l, int r, int x, int y){//((((( [0,l) + [l,r) + [r,x) + [x,y) + [y,n) ]]]]]vector<Node*> v = split_at(root, vector<int>{l,r,x,y});swap(v[1], v[3]);root = merge_vec(v);}//reverse range[l,r] -> [r,l]void reverse_range(int l, int r){vector<Node*> v = split_at(root, vector<int>{l,r+1});reverse(v[1]);root = merge_vec(v);}//add range [l,r].val += valvoid add_range(int l, int r, int val){vector<Node*> v = split_at(root, vector<int>{l,r+1});add(v[1], val);root = merge_vec(v);}//get minimum in range [l,r]Type get_range_min(int l, int r){vector<Node*> v = split_at(root, vector<int>{l,r+1});push(v[1]);Type ret = v[1]->sub_tree_min;root = merge_vec(v);return ret;}//get maxmum in range [l,r]Type get_range_max(int l, int r){vector<Node*> v = split_at(root, vector<int>{l,r+1});push(v[1]);Type ret = v[1]->sub_tree_max;root = merge_vec(v);return ret;}//get maxmum in range [l,r]Type get_range_sum(int l, int r){vector<Node*> v = split_at(root, vector<int>{l,r+1});push(v[1]);Type ret = v[1]->sub_tree_sum;root = merge_vec(v);return ret;}void get_all_value(Node* t, int offset, vector<Type> &v){if(t==NULL) return;push(t);int c = size(t->left);v[ c + offset ] = t->value;get_all_value( t->left, offset, v);get_all_value( t->right, c+1+offset, v);}void get_all_value(vector<Type> &v){get_all_value(root, 0, v);}//get [l,r)void get_range_value(Node* t, int offset, vector<Type> &v, const int &l, const int &r){if(t==NULL) return;push(t);int c = size(t->left);int pos = c+offset;if( l<= pos && pos < r ) v[ pos-l ] = t->value;if(offset < r && l <= pos-1) get_range_value( t->left, offset, v, l, r);if(pos+1 < r && l <= pos+size(t->right)) get_range_value( t->right, pos+1, v, l, r);}//get [l,r)void get_range_value(vector<Type> &v, const int &l, const int &r){get_range_value(root, 0, v, l, r);}};int main(){int n, m;cin >> n >> m;vector<int> A(m);for(int i=0; i<m; i++){cin >> A[i];A[i]--;}Treap<int> t;for(int i=0; i<n; i++){t.insert(i, i+1);}for(int i=0; i<m; i++){auto v = t.split_at(t.root, {A[i],A[i]+1});swap(v[0], v[1]);t.root = t.merge_vec(v);}int ans = t.find(0)->value;cout << ans << endl;return 0;}