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 |
|
|
|
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 |