BZOJ1012: [JSOI2008]最大数maxnumber

  1 //{HEADS
  2 #define FILE_IN_OUT
  3 #define debug
  4 #include <cstdio>
  5 #include <cstring>
  6 #include <cstdlib>
  7 #include <cmath>
  8 #include <ctime>
  9 #include <algorithm>
 10 #include <iostream>
 11 #include <fstream>
 12 #include <vector>
 13 #include <stack>
 14 #include <queue>
 15 #include <deque>
 16 #include <map>
 17 #include <set>
 18 #include <bitset>
 19 #include <complex>
 20 #include <string>
 21 #define REP(i, j) for (int i = 1; i <= j; ++i)
 22 #define REPI(i, j, k) for (int i = j; i <= k; ++i)
 23 #define REPD(i, j) for (int i = j; 0 < i; --i)
 24 #define STLR(i, con) for (int i = 0, sz = con.size(); i < sz; ++i)
 25 #define STLRD(i, con) for (int i = con.size() - 1; 0 <= i; --i)
 26 #define CLR(s) memset(s, 0, sizeof s)
 27 #define SET(s, v) memset(s, v, sizeof s)
 28 #define mp make_pair
 29 #define pb push_back
 30 #define PL(k, n) for (int i = 1; i <= n; ++i) { cout << k[i] << ‘ ‘; } cout << endl
 31 #define PS(k) STLR(i, k) { cout << k[i] << ‘ ‘; } cout << endl
 32 using namespace std;
 33 #ifdef debug
 34 #ifndef ONLINE_JUDGE
 35     const int OUT_PUT_DEBUG_INFO = 1;
 36 #endif
 37 #endif
 38 #ifdef ONLINE_JUDGE
 39     const int OUT_PUT_DEBUG_INFO = 0;
 40 #endif
 41 #define DG if(OUT_PUT_DEBUG_INFO)
 42 void FILE_INIT(string FILE_NAME) {
 43 #ifdef FILE_IN_OUT
 44 #ifndef ONLINE_JUDGE 
 45     freopen((FILE_NAME + ".in").c_str(), "r", stdin);
 46     freopen((FILE_NAME + ".out").c_str(), "w", stdout);
 47 
 48 #endif
 49 #endif
 50 }
 51 typedef long long LL;
 52 typedef double DB;
 53 typedef pair<int, int> i_pair;
 54 const int INF = 0x3f3f3f3f;
 55 //}
 56 
 57 const int maxn = 200000 + 10;
 58 
 59 int m, d;
 60 
 61 struct Things {
 62     int pos, val;
 63     Things() {}
 64     Things(int pos, int val):pos(pos), val(val) {}
 65     void print() {
 66         printf("%d %d\n", pos, val);
 67     }
 68 }S[maxn];
 69 int tail = 0;
 70 /*{ 获取字符*/
 71 char gchar() {
 72     char ret = getchar();
 73     for(; ret == ‘\n‘ || ret == ‘\r‘ || ret == ‘ ‘; ret = getchar());
 74     return ret;
 75 }
 76 /*}*/
 77 
 78 int main() {
 79     FILE_INIT("BZOJ1012");
 80 
 81     scanf("%d%d", &m, &d);
 82     char ope;
 83     int t, rec = 0, cnt = 0;
 84     REP(i, m) {
 85         ope = gchar();
 86         scanf("%d", &t);
 87         if(ope == ‘A‘) {
 88             S[++tail] = Things(++cnt, (rec + t) % d);
 89             DG S[tail].print();
 90             for(; 1 < tail && S[tail - 1].val <= S[tail].val; S[tail - 1] = S[tail], --tail);
 91             DG S[tail].print();
 92         } else {
 93             int l = 1, r = tail;
 94             DG printf("l = %d r = %d\n", l, r);
 95             while(l < r) {
 96                 int mid = (l + r) >> 1;
 97                 if(cnt - S[mid].pos + 1 <= t) {
 98                     r = mid;
 99                 } else {
100                     l = mid + 1;
101                 }
102             }
103             rec = S[l].val;
104             printf("%d\n", rec);
105         }
106     }
107 
108     return 0;
109 }