Acceleration of Network (KUPC 2012)

http://kupc2012.contest.atcoder.jp/tasks/kupc2012_6#

問題

略

解法

解説参照。

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <iostream>
#include <math.h>
#include <assert.h>
#include <vector>
#include <queue>
#include <string>
#include <map>
#include <set>

using namespace std;
typedef long long ll;
typedef unsigned int uint;
typedef unsigned long long ull;
static const double EPS = 1e-9;
static const double PI = acos(-1.0);

#define REP(i, n) for (ll i = 0; i < (ll)(n); i++)
#define FOR(i, s, n) for (ll i = (s); i < (ll)(n); i++)
#define FOREQ(i, s, n) for (ll i = (s); i <= (ll)(n); i++)
#define FORIT(it, c) for (__typeof((c).begin())it = (c).begin(); it != (c).end(); it++)
#define MEMSET(v, h) memset((v), h, sizeof(v))

const ll UPPER = 3652425;
int n, q;
ll vs[100010];
ll ts[100010];
ll xs[100010];
ll qs[100010];

ll serv[100010];
ll work[4000000];
ll ans[100010];
vector<int> end[4000000];

ll a, b, c;
void Push(ll sum, ll day, int &s) {
  while (s < n && vs[s] <= sum) {
    serv[s] = day;
    end[day + xs[s]].push_back(s);
    if (ts[s] == 0) {
      c++;
    } else if (ts[s] == 1) {
      b++;
      c -= day;
    } else if (ts[s] == 2) {
      a++;
      b -= 2 * day;
      c += day * day;
      assert(-2e+18 < b && b < 2e+18);
      assert(-2e+18 < c && c < 2e+18);
      assert(day == 0 || day * day / day == day);
    }
    s++;
  }
}

void Delete(ll day) {
  FORIT(it, end[day]) {
    int type = ts[*it];
    ll start = serv[*it];
    if (type == 0) {
      c--;
    } else if (type == 1) {
      b--;
      c += start;
    } else if (type == 2) {
      a--;
      b += 2 * start;
      c -= start * start;
    }
  }
}

int main() {
  while (scanf("%d %d", &n, &q) > 0) {
    // Init & Input
    MEMSET(serv, 0x0f);
    REP(i, 4000000) { end[i].clear(); }
    //MEMSET(work, 0);
    MEMSET(ans, 0);
    REP(i, n) {
      int v = scanf("%lld %lld %lld", &vs[i], &ts[i], &xs[i]);
      assert(v == 3);
    }
    REP(i, q) {
      int v = scanf("%lld", &qs[i]);
      assert(v == 1);
    }

    // Solve
    a = 0, b = 0, c = 1;
    ll sum = 0;
    int s = 0;
    int t = 0;
    Push(sum, 0, s);
    Delete(0);
    if (t < q && qs[t] == 0) { ans[t++] = sum; }
    FOREQ(day, 1, UPPER) {
      sum += a * day * day + b * day + c;
      work[day] = sum;
      assert(sum >= 0);
      assert(day == 0 || a * day * day / day == a * day);
      assert(day == 0 || b * day / day == b);

      if (t < q && qs[t] == day) { ans[t++] = sum; }
      Push(sum, day, s);
      Delete(day);
    }

    // Print Ans
    REP(i, n) {
      if (serv[i] <= UPPER) {
        printf("%lld\n", serv[i]);
      } else {
        printf("Many years later\n");
      }
    }
    REP(i, q) {
      printf("%lld\n", ans[i]);
    }
  }
}