poj 2153 Rank List

 1 #include<algorithm>

 2 #include<iostream>

 3 #include<cstdlib>

 4 #include<cstdio>

 5 #include<string>

 6 #include<map>

 7 using std::cin;

 8 using std::map;

 9 using std::string;

10 map<string, int> ret;

11 int main() {

12 #ifdef LOCAL

13     freopen("in.txt", "r", stdin);

14     freopen("out.txt", "w+", stdout);

15 #endif

16     string buf;

17     int n, m, v, tmp;

18     while (cin >> n) {

19         getchar();

20         for (int i = 0; i < n; i++) {

21             getline(cin, buf);

22             ret[buf] = 0;

23         }

24         cin >> m;

25         while (m--) {

26             int ans = 0;

27             for (int i = 0; i < n; i++) {

28                 cin >> v;

29                 getchar();

30                 getline(cin, buf);

31                 ret[buf] += v;

32             }

33             tmp = ret["Li Ming"];

34             map<string, int>::iterator ite;

35             for (ite = ret.begin(); ite != ret.end(); ++ite) {

36                 if (ite->second > tmp) ans++;

37             }

38             printf("%d
", ans + 1);

39         }

40         ret.clear();

41     }

42     return 0;

43 }

  1 #include<algorithm>

  2 #include<iostream>

  3 #include<cstdlib>

  4 #include<cstring>

  5 #include<cstdio>

  6 typedef char State[35];

  7 char *target = "Li Ming";

  8 const int Max_N = 11000;

  9 struct Node {

 10     State name;

 11     int data, s;

 12     bool color;

 13     Node *fa, *ch[2];

 14     inline void set(int _v, char *src, bool _color, int i, Node *p) {

 15         data = _v, color = _color, s = i;

 16         fa = ch[0] = ch[1] = p;

 17         strcpy(name, src);

 18     }

 19     inline void push_up() {

 20         s = ch[0]->s + ch[1]->s + 1;

 21     }

 22     inline int cmp(char *src) const {

 23         if (0 == strcmp(src, name)) return -1;

 24         else if (-1 == strcmp(src, name)) return 0;

 25         return 1;

 26     }

 27 };

 28 struct RedBlackTree {

 29     Node *root, *null;

 30     Node stack[Max_N], *tail;

 31     void init() {

 32         tail = &stack[0];

 33         null = tail++;

 34         null->set(0, "", 0, 0, NULL);

 35         root = null;

 36     }

 37     inline Node *newNode(char *name, int v) {

 38         Node *p = tail++;

 39         p->set(v, name, 1, 1, null);

 40         return p;

 41     }

 42     inline void rotate(Node* &x, bool d) {

 43         Node *y = x->ch[!d];

 44         x->ch[!d] = y->ch[d];

 45         if (y->ch[d] != null) y->ch[d]->fa = x;

 46         y->fa = x->fa;

 47         if (x->fa == null) root = y;

 48         else x->fa->ch[x->fa->ch[0] != x] = y;

 49         y->ch[d] = x;

 50         x->fa = y;

 51         y->s = x->s;

 52         x->push_up();

 53     }

 54     inline void insert(char *name, int v = 0) {

 55         int d = 0;

 56         Node *x = root, *y = null;

 57         while (x->s) {

 58             x->s++;

 59             d = x->cmp(name);

 60             y = x, x = x->ch[d];

 61         }

 62         x = newNode(name, v);

 63         if (y != null) { d = x->cmp(y->name), y->ch[!d] = x; }

 64         else root = x;

 65         x->fa = y;

 66         insert_fix(x);

 67     }

 68     inline void insert_fix(Node* &x) {

 69         while (x->fa->color){

 70             Node *par = x->fa, *Gp = par->fa;

 71             bool d = par == Gp->ch[0];

 72             Node *uncle = Gp->ch[d];

 73             if (uncle->color) {

 74                 par->color = uncle->color = 0;

 75                 Gp->color = 1;

 76                 x = Gp;

 77             } else if (x == par->ch[d]) {

 78                 rotate(x = par, !d);

 79             } else {

 80                 Gp->color = 1;

 81                 par->color = 0;

 82                 rotate(Gp, d);

 83             }

 84         }

 85         root->color = 0;

 86     }

 87     inline Node *find(Node *x, char *name) {

 88         while (x->s) {

 89             int d = x->cmp(name);

 90             if (-1 == d) break;

 91             x = x->ch[d];

 92         }

 93         return x;

 94     }

 95     inline void Modify(char *str, int v) {

 96         Node* ret = find(root, str);

 97         ret->data += v;

 98     }

 99     inline void dfs(Node *x, int v, int &ans) {

100         if (x != null){

101             dfs(x->ch[0], v, ans);

102             if (x->data > v) ans++;

103             dfs(x->ch[1], v, ans);

104         }

105     }

106     inline void query() {

107         int cnt = 0, ans = 0;

108         int v = find(root, target)->data;

109         dfs(root, v, ans);

110         printf("%d
", ans + 1);

111     }

112 }rbt;

113 int main(){

114 #ifdef LOCAL

115     freopen("in.txt", "r", stdin);

116     freopen("out.txt", "w+", stdout);

117 #endif

118     char buf[100];

119     int n, m, val;

120     while (~scanf("%d
", &n)) {

121         rbt.init();

122         for (int i = 0; i < n; i++) {

123             gets(buf);

124             rbt.insert(buf);

125         }

126         scanf("%d
", &m);

127         while (m--) {

128             for (int i = 0; i < n; i++) {

129                 gets(buf);

130                 sscanf(buf, "%d", &val);

131                 rbt.Modify(strchr(buf, ' ') + 1, val);

132             }

133             rbt.query();

134         }

135     }

136     return 0;

137 }