From http://www.lydsy.com/JudgeOnline/problem.php?id=1588
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 const static int N = 40001; 8 int v[N],l[N],r[N],p[N]; 9 int cnt, root; 10 void init(){ cnt = 0; root = 0; v[0]=l[0]=r[0]=p[0]=0;} 11 int alloc_node(int Val){ 12 v[++cnt] = Val; 13 l[cnt] = r[cnt] = p[cnt] = 0; 14 return cnt; 15 } 16 void rot_l(int x){ 17 int y = p[x]; 18 r[y] = l[x]; p[l[x]] = y; 19 p[x] = p[y]; 20 if ( !p[y] ) root = x; 21 else if ( y == l[p[y]] ) l[p[y]] = x; 22 else r[p[y]] = x; 23 l[x] = y; p[y] = x; 24 } 25 void rot_r(int x){ 26 int y = p[x]; 27 l[y] = r[x]; p[r[x]] = y; 28 p[x] = p[y]; 29 if ( !p[y] ) root = x; 30 else if ( y == l[p[y]] ) l[p[y]] = x; 31 else r[p[y]] = x; 32 r[x] = y; p[y] = x; 33 } 34 void maintain(int i){ 35 while ( p[i] ){ 36 if ( l[p[i]] == i ){ 37 if ( !p[p[i]] ) rot_r(i); // zig 38 else if ( l[p[p[i]]] == p[i] ){ //zig-zig 39 rot_r(p[i]); rot_r(i); 40 }else{ //zig-zag 41 rot_r(i); rot_l(i); 42 } 43 }else{ 44 if ( !p[p[i]] ) rot_l(i); 45 else if ( r[p[p[i]]] == p[i] ){ 46 rot_l(p[i]); rot_l(i); 47 }else{ 48 rot_l(i); rot_r(i); 49 } 50 } 51 } 52 } 53 int insert(int Val){ 54 int k = alloc_node(Val); 55 int i = root, j = p[root]; 56 while ( i ) { 57 j = i; 58 if ( v[i] == Val ){ 59 maintain(i); 60 return 0; 61 } 62 if ( v[i] < Val ) i = r[i]; 63 else i = l[i]; 64 } 65 66 p[k] = j; 67 if ( j == 0 ) root = k; 68 else if ( v[j] < Val ) r[j] = k; 69 else l[j] = k; 70 maintain(k); 71 return 1; 72 } 73 int prev(){ 74 int y = l[root]; 75 while ( r[y] ) y = r[y]; 76 return y; 77 } 78 int succ(){ 79 int y = r[root]; 80 while ( l[y] ) y = l[y]; 81 return y; 82 } 83 84 #define ABS(x) (((x)<0)?(-(x)):(x)) 85 int main() 86 { 87 //const char path[] = "D:\\Project\\AlgorithmExam\\test.txt"; 88 //freopen(path, "r+", stdin); 89 90 int n; 91 while ( scanf("%d", &n) != EOF ){ 92 init(); 93 int m; 94 long long sum = 0; 95 for ( int i = 0; i < n; ++i ){ 96 if ( scanf("%d", &m) == EOF ) m = 0; 97 if ( !insert(m) ) continue; 98 int x = prev(); 99 int y = succ();100 if ( 0 == x && y == 0 ) sum += m;101 else if ( 0 == x ) sum += ABS(v[y]-m);102 else if ( 0 == y ) sum += ABS(v[x]-m);103 else sum += min(ABS(v[y]-m), ABS(v[x]-m));104 }105 printf("%lld\n", sum);106 }107 return 0;108 }
1 /************************************************************** 2 Problem: 1588 3 User: leezy 4 Language: C++ 5 Result: Accepted 6 Time:156 ms 7 Memory:2260 kb 8 ****************************************************************/ 9 10 #include11 #include 12 #include 13 #include 14 #define N 4001515 #define M 100000016 #define INF 0x6fffffff17 #define MAX_LEVEL 3218 #define NIL (0)19 #define min(a,b) ((a)<(b))?(a):(b)20 typedef struct tagSkipListNode{21 int key;22 tagSkipListNode* next, *prev, *up, *down;23 } Node;24 Node Nil;25 Node* List[MAX_LEVEL], *Upd[MAX_LEVEL];26 int top;27 void Init(int x)28 {29 top = -1;30 Nil.key = INF;31 srand(x);32 }33 Node* NewNode(int key){34 Node* p = (Node*)malloc(sizeof(Node));35 p->key = key;36 p->prev = p->next = &Nil;37 p->up = p->down = &Nil;38 return p;39 }40 int Find_LessEqual(int key){41 if ( top < 0 ) return 0;42 int k = top;43 Node* p = List[k];44 while ( k >= 0 ){45 for (Node* q = p->next; q->key <= key; p = q, q = p->next );46 Upd[k--] = p;47 p = p->down;48 }49 return (Upd[0]->key == key)?(1):(0);50 }51 int Ins(int key){52 if ( Find_LessEqual(key) ) return 0;53 int k = 0;54 for (float r = 0; r < 0.5 && k < MAX_LEVEL; r = ((float)rand())/RAND_MAX) { ++k; }55 for (; top + 1 < k; ){56 Node* p = NewNode(-INF);57 if ( -1 == top ) List[++top] = p;58 else {59 List[top]->up = p; p->down = List[top];60 List[++top] = p;61 }62 Upd[top] = p;63 }64 Node* top2 = 0;65 for (int i = 0; i < k; ++i ){66 Node* p = NewNode(key);67 Node* q = Upd[i]->next;68 p->next = q; q->prev = p;69 Upd[i]->next = p; p->prev = Upd[i];70 if ( !top2 ) top2 = p;71 else {72 p->down = top2; top2->up = p;73 top2 = p;74 }75 }76 77 Node* x = Upd[0], *y = x->next, *z = y->next;78 if ( x->key == -INF && z->key == INF ) return y->key;79 if ( x->key == -INF && z->key != INF ) return abs(y->key-z->key);80 if ( x->key != -INF && z->key == INF ) return abs(x->key-y->key);81 return min(abs(x->key-y->key), abs(y->key-z->key));82 }83 int main()84 {85 int n, sum = 0;86 while ( scanf("%d", &n) != EOF ){87 //char op[5];88 Init(n+sum);89 sum = 0;90 for ( int i = 0; i < n; ++i ){91 int d = 0;92 if ( scanf("%d", &d) == EOF ) d = 0;93 sum += Ins(d);94 //Dump();95 }96 printf("%d\n", sum);97 }98 return 0;99 }