Submission #1179804

---

Source Code Expand

#include<bits/stdc++.h>

using namespace std;

typedef long long int64;
const int64 INF = 1LL << 58;

const int backet = 333;

int Q, K;
int64 T[100001], D[100001], A[100001];
vector< int64 > nums;
int64 sum[100001], small[100001], sub[100001];

void push(int k)
{
  small[k] = INF;
  for(int i = k * backet; i < min((int) nums.size(), (k + 1) * backet); i++) {
    sum[i] -= sub[k];
    small[k] = min(small[k], sum[i]);
  }
  sub[k] = 0;
}

int main()
{
  cin >> Q >> K;
  for(int i = 0; i < Q; i++) {
    cin >> T[i] >> D[i];
    if(T[i] == 1) cin >> A[i];
    nums.push_back(D[i]);
  }
  nums.push_back(0);
  sort(begin(nums), end(nums));
  nums.erase(unique(begin(nums), end(nums)), end(nums));
  int all = (nums.size() + backet - 1) / backet;

  for(int i = 0; i < Q; i++) {
    D[i] = lower_bound(begin(nums), end(nums), D[i]) - begin(nums);
  }

  for(int i = 1; i < nums.size(); i++) {
    sum[i] = nums[i] * K;
  }
  for(int j = 0; j < all; j++) {
    small[j] = sum[j * backet];
  }


  for(int i = 0; i < Q; i++) {
    if(T[i] == 2) {
      push(i / backet);
      cout << nums[D[i]] * K - sum[D[i]] << endl;
    } else {
      int64 dec = A[i];
      int64 a = D[i], b = (int) nums.size();
      for(int j = 0; j < all; j++) {
        int64 l = j * backet, r = min((int) nums.size(), (j + 1) * backet);
        if(a >= r || b <= l) continue;
        if(a <= l && r <= b) {
          dec = min(dec, small[j] - sub[j]);
          sub[j] += dec;
        } else {
          push(j);
          for(int64 k = max(a, l); k < min(b, r); k++) {
            dec = min(dec, sum[k]);
            sum[k] -= dec;
            small[j] = min(small[j], sum[k]);
          }
        }
      }
    }
  }


}

Submission Info

Judge Result