Submission #1152510
Source Code Expand
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;
#define rep(i,n) for(int i=0;i<n;i++)
#define rrep(i,n) for(int i=n-1;i>=0;i--)
#define mp make_pair
#define fst first
#define scn second
vector<ll> dls;
class SegmentTree {
public:
vector<pll> segt;
int size;
void init(int n,ll k) {
size = 1;
while (size < n) size *= 2;
segt.resize(2*size);
for (int i = 1; i < 2 * size; i++) segt[i] = mp(0, 0);
rep(i, dls.size()) {
if (i) segt[i + size] = mp(k*(dls[i] - dls[i - 1]), 0);
else segt[i + size] = mp(k*dls[i], 0);
}
for (int i = size - 1; i > 0; i--) {
segt[i].fst = segt[2 * i].fst + segt[2 * i + 1].fst;
segt[i].scn = max(segt[2 * i].scn + segt[2 * i + 1].fst, segt[2 * i + 1].scn);
}
}
/* max(a+x,b),max(c+x,d)のノードの親max(ex,f)は、
max(e+x,f)=max(c+max(a+x,b),d)=max(a+c+x,max(b+c,d))より
e=a+c,f=max(b+c,d)
*/
void addUpdate(int i, ll v) {
i += size;
segt[i].fst += v;
while (i>1) {
i /= 2;
segt[i].fst = segt[2 * i].fst + segt[2 * i + 1].fst;
segt[i].scn = max(segt[2 * i].scn + segt[2 * i + 1].fst, segt[2 * i + 1].scn);
}
}
ll query(int l, int r, int a, int b, int i, ll ret) {
if (r <= a || b <= l) return ret;
if (a <= l&&r <= b) return max(segt[i].fst + ret, segt[i].scn);
int m = (l + r) / 2;
ret = query(l, m, a, b, 2 * i, ret);
return query(m, r, a, b, 2 * i + 1, ret);
}
}segt;
int main() {
ll n, k; cin >> n >> k;
vector<ll> type(n), d(n), a(n);
rep(i, n) {
cin >> type[i];
if (type[i] == 1) {
cin >> d[i] >> a[i];
}
else {
cin >> d[i];
}
dls.push_back(d[i]);
}
sort(dls.begin(), dls.end());
dls.erase(unique(dls.begin(), dls.end()), dls.end());
segt.init(dls.size(),k);
rep(i, n) {
int pos = distance(dls.begin(), lower_bound(dls.begin(), dls.end(), d[i]));
if (type[i] == 1) {
segt.addUpdate(pos, -a[i]);
}
else {
cout << k*d[i] - segt.query(0, segt.size, 0, pos + 1, 1, 0) << endl;
}
}
return 0;
}
Submission Info
Submission Time |
|
Task |
D - 工場 |
User |
fiord |
Language |
C++14 (GCC 5.4.1) |
Score |
1000 |
Code Size |
2111 Byte |
Status |
AC |
Exec Time |
197 ms |
Memory |
8308 KB |
Judge Result
Set Name |
Sample |
subtask |
All |
Score / Max Score |
0 / 0 |
600 / 600 |
400 / 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 |
AC |
172 ms |
6004 KB |
in10.txt |
AC |
191 ms |
8308 KB |
in11.txt |
AC |
195 ms |
8180 KB |
in12.txt |
AC |
190 ms |
8180 KB |
in13.txt |
AC |
190 ms |
8180 KB |
in14.txt |
AC |
192 ms |
8180 KB |
in15.txt |
AC |
192 ms |
8180 KB |
in16.txt |
AC |
154 ms |
4084 KB |
in17.txt |
AC |
154 ms |
4084 KB |
in18.txt |
AC |
155 ms |
4084 KB |
in19.txt |
AC |
154 ms |
4084 KB |
in2.txt |
AC |
175 ms |
6004 KB |
in20.txt |
AC |
153 ms |
4084 KB |
in21.txt |
AC |
186 ms |
8052 KB |
in22.txt |
AC |
183 ms |
8052 KB |
in23.txt |
AC |
158 ms |
4340 KB |
in24.txt |
AC |
159 ms |
4340 KB |
in25.txt |
AC |
158 ms |
4340 KB |
in3.txt |
AC |
175 ms |
6004 KB |
in4.txt |
AC |
174 ms |
6004 KB |
in5.txt |
AC |
174 ms |
6004 KB |
in6.txt |
AC |
193 ms |
8308 KB |
in7.txt |
AC |
192 ms |
8308 KB |
in8.txt |
AC |
197 ms |
8308 KB |
in9.txt |
AC |
192 ms |
8308 KB |
sample1.txt |
AC |
1 ms |
256 KB |
sample2.txt |
AC |
1 ms |
256 KB |
sample3.txt |
AC |
1 ms |
256 KB |
subin1.txt |
AC |
163 ms |
8052 KB |
subin10.txt |
AC |
163 ms |
8052 KB |
subin11.txt |
AC |
161 ms |
8052 KB |
subin12.txt |
AC |
162 ms |
8052 KB |
subin13.txt |
AC |
161 ms |
8052 KB |
subin14.txt |
AC |
161 ms |
8052 KB |
subin15.txt |
AC |
163 ms |
8052 KB |
subin16.txt |
AC |
158 ms |
4340 KB |
subin17.txt |
AC |
160 ms |
4340 KB |
subin18.txt |
AC |
158 ms |
4340 KB |
subin19.txt |
AC |
158 ms |
4340 KB |
subin2.txt |
AC |
161 ms |
8052 KB |
subin3.txt |
AC |
162 ms |
8052 KB |
subin4.txt |
AC |
162 ms |
8052 KB |
subin5.txt |
AC |
161 ms |
8052 KB |
subin6.txt |
AC |
163 ms |
8052 KB |
subin7.txt |
AC |
161 ms |
8052 KB |
subin8.txt |
AC |
163 ms |
8052 KB |
subin9.txt |
AC |
161 ms |
8052 KB |