Problem 2029 買票問題
Accept: 8 Submit: 56
Time Limit: 5000 mSec Memory Limit : 32768 KB
Problem Description
過年回家買票又排起了長隊。剛開始隊列為空的。 有四種情況： 1.隊尾加進了一個編號為a，忍耐度為 b 的人，所有人的編號都不同。 2.隊首的人買完票走了。 3.隊列中忍耐度最低的人離開了隊列。 4.在隊伍變化的過程中，編號為x的人想知道他前面有多少人,如果人數大于 y 則他離開隊伍。 所有人的編號和忍耐度都是一個整數(保證可以使用有符號32位整型保存)，且都是唯一的。
Input
輸入數據包含多組測試數據輸入數據第一行T表示操作的個數。(T <= 100000) 接著T行， add a b 表示隊伍尾加入 編號a忍耐度b的人(a,b保證可以使用有符號32位整型保存) pop 隊首的人買完票走了,如果隊列為空則不執行此操作。 leave 隊列中忍耐度最低的人離開了隊列,如果隊列為空則不執行此操作。 check x y在隊伍變化的過程中，編號為x的人想知道他前面有多少人,如果人數大于 y 則他離開隊伍,如果隊列不含編號為x的人不執行此操作。(x,y保證可以使用有符號32位整型保存)
Output
對于第四種操作 輸出編號為x的人前面的人數。
Sample Input
10
add 5 1
add 4 2
add 3 3
add 2 4
add 1 5
check 2 5
leave
check 2 1
pop
check 1 5
Sample Output
3
2
1
小根堆求最小值，樹狀數組求個數，map 求映射（注意加注釋的幾個erase，沒有就超時，鄙視卡常數的！！！！）。
1
#include <iostream>
2#include <cstdio>
3#include <vector>
4#include <queue>
5#include <cstring>
6#include <map>
7
8using namespace std;
9
10const int T = 100009;
11
12struct Peo
13
{
14
Peo( int _a=0, int _b=0, int _q=0 ) : a(_a), b(_b), q(_q) {}
15
int a, b, q;
16
};
17
18class MinCmp
19{
20public :
21 bool operator()( const Peo &a, const Peo &b );
22};
23bool MinCmp::operator()( const Peo &a, const Peo &b ) {
24 return a.b > b.b;
25}
26
27int qh, qt, inq[ T ], sq[ T ], q2a[ T ];
28map< int, int > a2q;
29priority_queue< Peo, vector< Peo >, MinCmp > heap;
30
31#define lowbit(i) (i&((i-1)^i))
32
33void st_add( int i, int delta ) {
34 while ( i < T ) {
35 sq[ i ] += delta;
36 i += lowbit(i);
37
}
38}
39
40int st_sum( int i ) {
41 int s = 0;
42 while ( i > 0 ) {
43 s += sq[ i ];
44 i -= lowbit( i );
45 }
46 return s;
47}
48
49void init() {
50 while ( ! heap.empty() ) {
51 heap.pop();
52 }
53 qh = qt = 1;
54 a2q.clear();
55 memset( inq, 0, sizeof(inq) );
56 memset( sq, 0, sizeof(sq) );
57}
58
59void add( int a, int b ) {
60 a2q[ a ] = qt;
61 q2a[ qt ] = a;
62 heap.push( Peo( a, b, qt ) );
63 inq[ qt ] = 1;
64 st_add( qt, 1 );
65 ++qt;
66}
67
68void pop() {
69 while ( (qh<qt) && (inq[qh]==0) ) {
70 ++qh;
71 }
72 if ( qh < qt ) {
73 inq[ qh ] = 0;
74 a2q.erase( q2a[ qh ] );/**/////////////////////////////
75 st_add( qh, -1 );
76 ++qh;
77 }
78}
79
80void leave() {
81 Peo p;
82 while ( (!heap.empty()) && (inq[heap.top().q]==0) ) {
83 heap.pop();
84 }
85 if ( !heap.empty() ) {
86 p = heap.top();
87 inq[ p.q ] = 0;
88 st_add( p.q, -1 );
89 a2q.erase( q2a[ p.q ] );/**//////////////////////////////////
90 }
91}
92
93void check( int x, int y ) {
94 map< int, int >::iterator ite = a2q.find( x );
95 if ( ite != a2q.end() ) {
96 int q = ite->second;
97 int s = st_sum( q ) - 1;
98 printf( "%d\n", s );
99 if ( s > y ) {
100 inq[ q ] = 0;
101 st_add( q, -1 );
102 a2q.erase( ite );/**/////////////////////////////
103 }
104 }
105}
106
107int main() {
108 int t, a, b;
109 char cmd[ 100 ];
110 while ( scanf( "%d", &t ) == 1 ) {
111 init();
112 while ( t-- > 0 ) {
113 scanf( "%s", cmd );
114 if ( cmd[ 0 ] == 'a' ) {
115 scanf( "%d%d", &a, &b );
116 add( a, b );
117 }
118 else if ( cmd[ 0 ] == 'p' ) {
119 pop();
120 }
121 else if ( cmd[ 0 ] == 'l' ) {
122 leave();
123 }
124 else if ( cmd[ 0 ] == 'c' ) {
125 scanf( "%d%d", &a, &b );
126 check( a, b );
127 }
128 }
129 }
130 return 0;
131}
132