本文共 4302 字，大约阅读时间需要 14 分钟。
Treap+set仿函数重定义。每当ac一道题目时，相当于对总时间减去一个大数。
1 /* 5096 */ 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 #include 14 #include 15 #include 16 #include 17 #include 18 #include 19 #include 20 #include 21 using namespace std; 22 //#pragma comment(linker,"/STACK:102400000,1024000") 23 24 #define sti set 25 #define stpii set > 26 #define mpii map 27 #define vi vector 28 #define pii pair 29 #define vpii vector > 30 #define rep(i, a, n) for (int i=a;i =a;--i) 32 #define clr clear 33 #define pb push_back 34 #define mp make_pair 35 #define fir first 36 #define sec second 37 #define all(x) (x).begin(),(x).end() 38 #define SZ(x) ((int)(x).size()) 39 #define lson l, mid, rt<<1 40 #define rson mid+1, r, rt<<1|1 41 42 const int maxn = 10005; 43 const int BigInt = 1e7; 44 int S[maxn], top, tot, root; 45 int lst[maxn], lstac[maxn]; 46 bool mark[maxn][15]; 47 int pen[maxn][15]; 48 int T[maxn]; 49 char cmd[10], line[1005]; 50 51 typedef struct fcmp { 52 bool operator() (const int& a, const int& b) { 53 if (lstac[a]==-1 && lstac[b]==-1) 54 return a st; 68 69 Node() {} 70 71 void setId(int v_, int id) { 72 v = v_; 73 st.clr(); 74 st.insert(id); 75 ch[0] = ch[1] = 0; 76 r = rand(); 77 s = c = 1; 78 } 79 80 int cmp(int x) const { 81 if (x == v) return -1; 82 return x nd[r].r)132 Rotate(r, d^1);133 }134 maintain(r);135 }136 137 void Remove(int& r, int id, int v) {138 int d = nd[r].cmp(v);139 140 if (d == -1) {141 if (nd[r].c > 1) {142 --nd[r].c;143 --nd[r].s;144 nd[r].erase(id);145 return ;146 }147 148 if (nd[r].ch[0] && nd[r].ch[1]) {149 int d2 = nd[nd[r].ch[0]].r > nd[nd[r].ch[1]].r ? 1:0;150 Rotate(r, d2);151 Remove(nd[r].ch[d2], id, v);152 } else {153 S[top++] = r;154 r = nd[r].ch[1] + nd[r].ch[0];155 }156 } else {157 Remove(nd[r].ch[d], id, v);158 }159 160 if (r)161 maintain(r);162 }163 164 void init() {165 nd[0].ch[0] = nd[0].ch[1] = nd[0].s = nd[0].v = nd[0].c = 0;166 memset(pen, 0, sizeof(pen));167 memset(mark, false, sizeof(mark));168 memset(lst, -1, sizeof(lst));169 memset(lstac, -1, sizeof(lstac));170 memset(T, 0, sizeof(T));171 top = tot = root = 0;172 }173 174 int Rank(int r, int v) {175 int d = nd[r].cmp(v);176 int sz = nd[nd[r].ch[0]].s;177 178 if (d == -1)179 return sz+1;180 else if (d == 0)181 return Rank(nd[r].ch[0], v);182 else183 return sz+nd[r].c+Rank(nd[r].ch[1], v);184 }185 186 int kth(int r, int k) {187 if (r==0 || k<=0 || k>nd[r].s) return -1;188 int sz = nd[nd[r].ch[0]].s;189 190 if (k <= sz) {191 return kth(nd[r].ch[0], k);192 } else if (k <= sz+nd[r].c) {193 if (k == sz+1) {194 return *nd[r].st.begin();195 } else {196 return -1;197 }198 } else {199 return kth(nd[r].ch[1], k-sz-nd[r].c);200 }201 202 }203 204 int main() {205 ios::sync_with_stdio(false);206 #ifndef ONLINE_JUDGE207 freopen("data.in", "r", stdin);208 freopen("data.out", "w", stdout);209 #endif210 211 int n, m;212 int ino;213 int t, k, tno, res, pid;214 int ans;215 216 while (scanf("%d %d", &n, &m)!=EOF) {217 init();218 ino = 0;219 rep(i, 0, n) {220 Insert(root, i, 0);221 }222 while (1) {223 scanf("%s %s", cmd, line);224 ++ino;225 if (cmd[0] == 'C')226 break;227 if (cmd[0] == 'T') {228 int len = strlen(line);229 int i = 0;230 231 k = 0;232 while (i < len) {233 k = 10 * k + line[i]-'0';234 ++i;235 }236 ans = kth(root, k);237 printf("%d\n", ans);238 } else if (cmd[0] == 'R') {239 int len = strlen(line);240 int i = 0;241 242 tno = 0;243 while (i < len) {244 tno = 10 * tno + line[i]-'0';245 ++i;246 }247 t = T[tno];248 ans = Rank(root, t);249 printf("%d\n", ans);250 } else if (cmd[0] == 'S') {251 int len = strlen(line);252 int i = 0;253 254 t = 0;255 while (i =0 && t-lst[tno]<5)280 continue;281 if (res != 1) {282 pen[tno][pid] += 20;283 lst[tno] = t;284 continue;285 }286 printf("[%d][%c]\n", tno, pid+'A');287 Remove(root, tno, T[tno]);288 T[tno] += pen[tno][pid];289 T[tno] += t;290 mark[tno][pid] = true;291 T[tno] -= BigInt;292 lst[tno] = t;293 lstac[tno] = ino;294 Insert(root, tno, T[tno]);295 }296 }297 putchar('\n');298 }299 300 #ifndef ONLINE_JUDGE301 printf("time = %d.\n", (int)clock());302 #endif303 304 return 0;305 }
转载于:https://www.cnblogs.com/bombe1013/p/4909379.html