Submission #1179844


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], logs[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(D[i] / backet);
      cout << nums[D[i]] * K - sum[D[i]] << endl;
    } else {
      int64 dec = A[i];
      logs[D[i]] += 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

Submission Time
Task D - 工場
User ei13333
Language C++14 (GCC 5.4.1)
Score 600
Code Size 1816 Byte
Status WA
Exec Time 372 ms
Memory 6004 KB

Judge Result

Set Name Sample subtask All
Score / Max Score 0 / 0 600 / 600 0 / 400
Status
AC × 3
AC × 20
AC × 35
WA × 15
Set Name Test Cases
Sample sample1.txt, sample2.txt, sample3.txt
subtask sample2.txt, subin1.txt, subin10.txt, subin11.txt, subin12.txt, subin13.txt, subin14.txt, subin15.txt, subin16.txt, subin17.txt, subin18.txt, subin19.txt, subin2.txt, subin3.txt, subin4.txt, subin5.txt, subin6.txt, subin7.txt, subin8.txt, subin9.txt
All sample1.txt, sample2.txt, sample3.txt, in1.txt, in10.txt, in11.txt, in12.txt, in13.txt, in14.txt, in15.txt, in16.txt, in17.txt, in18.txt, in19.txt, in2.txt, in20.txt, in21.txt, in22.txt, in23.txt, in24.txt, in25.txt, in3.txt, in4.txt, in5.txt, in6.txt, in7.txt, in8.txt, in9.txt, sample1.txt, sample2.txt, sample3.txt, subin1.txt, subin10.txt, subin11.txt, subin12.txt, subin13.txt, subin14.txt, subin15.txt, subin16.txt, subin17.txt, subin18.txt, subin19.txt, subin2.txt, subin3.txt, subin4.txt, subin5.txt, subin6.txt, subin7.txt, subin8.txt, subin9.txt
Case Name Status Exec Time Memory
in1.txt WA 247 ms 5492 KB
in10.txt AC 283 ms 6004 KB
in11.txt WA 279 ms 6004 KB
in12.txt WA 281 ms 6004 KB
in13.txt WA 283 ms 6004 KB
in14.txt WA 283 ms 6004 KB
in15.txt WA 283 ms 6004 KB
in16.txt WA 206 ms 5236 KB
in17.txt WA 206 ms 5236 KB
in18.txt WA 206 ms 5236 KB
in19.txt WA 206 ms 5236 KB
in2.txt WA 248 ms 5492 KB
in20.txt WA 206 ms 5236 KB
in21.txt AC 274 ms 5748 KB
in22.txt AC 275 ms 5748 KB
in23.txt AC 211 ms 5108 KB
in24.txt AC 214 ms 5108 KB
in25.txt AC 210 ms 5108 KB
in3.txt WA 247 ms 5620 KB
in4.txt WA 253 ms 5620 KB
in5.txt WA 249 ms 5620 KB
in6.txt AC 282 ms 6004 KB
in7.txt AC 280 ms 6004 KB
in8.txt AC 284 ms 6004 KB
in9.txt AC 289 ms 6004 KB
sample1.txt AC 2 ms 2304 KB
sample2.txt AC 2 ms 2304 KB
sample3.txt AC 2 ms 2304 KB
subin1.txt AC 253 ms 5620 KB
subin10.txt AC 259 ms 5620 KB
subin11.txt AC 248 ms 5620 KB
subin12.txt AC 259 ms 5620 KB
subin13.txt AC 372 ms 5620 KB
subin14.txt AC 248 ms 5620 KB
subin15.txt AC 255 ms 5620 KB
subin16.txt AC 211 ms 5108 KB
subin17.txt AC 211 ms 5108 KB
subin18.txt AC 211 ms 5108 KB
subin19.txt AC 211 ms 5108 KB
subin2.txt AC 245 ms 5620 KB
subin3.txt AC 250 ms 5620 KB
subin4.txt AC 258 ms 5620 KB
subin5.txt AC 248 ms 5620 KB
subin6.txt AC 259 ms 5620 KB
subin7.txt AC 253 ms 5620 KB
subin8.txt AC 251 ms 5620 KB
subin9.txt AC 257 ms 5620 KB