CodeChef submission 108475 (C++ 4.0.0-8) plaintext list. Status: AC, problem H5, contest OCT09. By pmnox (pmnox), 2009-10-11 08:28:40.
#include <cstdio>
#include <algorithm>
#include <vector>
#include <set>
#include <map>
#include <string>
#include <numeric>
#include <cmath>
#include <cstdlib>
#include <iostream>
#include <sstream>
#include <cstring>
using namespace std;
 
#define rep(i,b) for(int i=(0);i<(b);++i)
#define fo(i,a,b) for(int i=(a);i<=(b);++i)
#define ford(i,a,b) for(int i=(a);i>=(b);--i)
#define fore(a,b) for(__typeof((b).begin()) a = (b).begin();a!=(b).end();++a)
#define vv vector
#define pb push_back
#define ll long long
#define ld long double
#define ss(a) (int)(a).size()
#define all(x) (x).begin(),(x).end()
#define clr(x,a) memset(x,a,sizeof(x))
#define vi vv<int>
#define vs vv<string>
 
int cond = (ll)1;
#define db(x) { if (cond > 0) { cond--; rep (xxx, 1) cerr << __LINE__ << " " << #x << " " << x << endl; cerr.flush(); } }
 
const int sz = 1<<16;
ll dp[sz<<1];
int m, n;
 
void change(int p, int val) {
    p += sz;
    dp[p] = val;
    p /= 2;
    while (p >= 1)
    {
        dp[p] = dp[2 * p] + dp[2 * p + 1];
        p /= 2;
    }
}
 
void findit(int atleast, int &nsum, int &ncur) {
    int p = 1;
    nsum = 0;
    while (p < sz) {
        if (nsum + dp[2*p] > atleast)
            p = 2 * p;
        else {
            nsum += dp[2*p];
            p = 2 * p + 1;
        }
    }
    ncur = p - sz;
}
 
void solve() {
    {
        scanf("%d%d", &m, &n);
        rep (i, sz<<1) dp[i] = 0;
        rep (i, n) scanf("%lld", &dp[sz+i]);
 
        fo (i, n, sz-1) dp[sz+i] = m;
        rep (i, sz) dp[sz+i]++;
        m++;
 
        ford (i, sz - 1, 1) dp[i] = dp[2*i] + dp[2*i+1];
    }
    {
        while (1) {
            char rozkaz = 0;
            scanf("%c", &rozkaz);
            if (rozkaz == 'E') break;
            else if (rozkaz == 'C') {
                int i, l;
                scanf("%d%d", &i, &l); i--;
                change(i, l + 1);
            }
            else if (rozkaz == 'I') {
                int i;
                scanf("%d", &i); i--;
                int page = 0; int cur = 0; int sum = 0;
                while (cur <= i) {
                    page++;
                    findit(sum + m, sum, cur);
                    db(sum<<" "<<cur<<" "<<i+1);
                }
                printf("%d\n", page);
            }
        }
    }
 
 
}
 
int main(int argc, char ** argv) {
    ios::sync_with_stdio(false);
    cond = argc >= 2 && argv[1][0] == 'q' ? 1 << 30 : 0;
    int t;
    scanf("%d", &t);
    fo (i, 1, t) {
        printf("Case #%d:\n", i);
        solve();
        printf("\n");
    }
 
    return 0;
}