Submission #2979258
Source Code Expand
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int MAXN = 1e5 + 5;
int n, q;
int ql, qr;
LL qv;
LL mv[MAXN << 2];
LL add[MAXN << 2];
void pushdown(int o) {
if (add[o]) {
mv[o << 1] += add[o];
mv[o << 1 | 1] += add[o];
add[o] = 0;
}
}
void maintain(int o) {
mv[o] = max(mv[o << 1], mv[o << 1 | 1]);
}
void build(int o, int l, int r) {
if (l == r) {
mv[o] = l - 1;
add[o] = 0;
return;
}
int mid = (l+r)>>1;
build(o<<1, l, mid);
build(o<<1|1, mid + 1, r);
maintain(o);
}
void _add(int o, int l, int r) {
if (ql <= l && r <= qr) {
mv[o] += qv;
add[o] += qv;
return;
}
pushdown(o);
int mid = (l + r) >> 1;
if (ql <= mid) _add(o<<1, l, mid);
if (mid < qr) _add(o<<1|1, mid + 1, r);
maintain(o);
}
void _query(int o, int l, int r) {
if (ql <= l && r <= qr) {
qv = max(qv, mv[o]);
return;
}
pushdown(o);
int mid = (l + r) >> 1;
if (ql <= mid) _query(o<<1, l, mid);
if (mid < qr) _query(o<<1|1, mid + 1, r);
}
void seg_add(int l, int r, LL v) {
ql = l, qr = r, qv = v;
_add(1, 1, n);
}
LL seg_query(int l, int r) {
ql = l, qr = r, qv = 0;
_query(1, 1, n);
return qv;
}
int main()
{
scanf("%d%d", &n, &q);
build(1, 1, n);
int ll = n;
int rr = 1;
while (q--) {
int l, r, v;
scanf("%d%d%d", &l, &r, &v);
seg_add(l, r, v);
ll = min(ll, l);
rr = max(rr, r);
printf("%lld\n", seg_query(ll, rr));
}
return 0;
}
Submission Info
Submission Time |
|
Task |
K - Conveyor Belt |
User |
lyxin65 |
Language |
C++14 (GCC 5.4.1) |
Score |
0 |
Code Size |
1489 Byte |
Status |
WA |
Exec Time |
94 ms |
Memory |
7552 KB |
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:75:23: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d", &n, &q);
^
./Main.cpp:81:30: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d%d%d", &l, &r, &v);
^
Judge Result
Set Name |
All |
Score / Max Score |
0 / 100 |
Status |
|
Set Name |
Test Cases |
All |
00_sample_00, 00_sample_01, 00_sample_02, 00_sample_03, 10_small-rand_0, 10_small-rand_1, 10_small-rand_2, 10_small-rand_3, 10_small-rand_4, 10_small-rand_5, 10_small-rand_6, 10_small-rand_7, 10_small-rand_8, 10_small-rand_9, 20_large-rand_0, 20_large-rand_1, 20_large-rand_2, 20_large-rand_3, 20_large-rand_4, 20_large-rand_5, 20_large-rand_6, 20_large-rand_7, 20_large-rand_8, 20_large-rand_9, 50_smallval-rand_0, 50_smallval-rand_1, 50_smallval-rand_10, 50_smallval-rand_11, 50_smallval-rand_12, 50_smallval-rand_13, 50_smallval-rand_14, 50_smallval-rand_15, 50_smallval-rand_16, 50_smallval-rand_17, 50_smallval-rand_18, 50_smallval-rand_19, 50_smallval-rand_2, 50_smallval-rand_3, 50_smallval-rand_4, 50_smallval-rand_5, 50_smallval-rand_6, 50_smallval-rand_7, 50_smallval-rand_8, 50_smallval-rand_9, 60_smallpart-rand_0, 60_smallpart-rand_1, 60_smallpart-rand_2, 60_smallpart-rand_3, 60_smallpart-rand_4, 60_smallpart-rand_5, 60_smallpart-rand_6, 60_smallpart-rand_7, 60_smallpart-rand_8, 60_smallpart-rand_9, 70_smallpart-rand_0 |
Case Name |
Status |
Exec Time |
Memory |
00_sample_00 |
AC |
1 ms |
2304 KB |
00_sample_01 |
AC |
1 ms |
2304 KB |
00_sample_02 |
AC |
1 ms |
2304 KB |
00_sample_03 |
AC |
2 ms |
2304 KB |
10_small-rand_0 |
WA |
1 ms |
2304 KB |
10_small-rand_1 |
WA |
1 ms |
2304 KB |
10_small-rand_2 |
AC |
1 ms |
2304 KB |
10_small-rand_3 |
WA |
1 ms |
2304 KB |
10_small-rand_4 |
WA |
1 ms |
2304 KB |
10_small-rand_5 |
WA |
1 ms |
2304 KB |
10_small-rand_6 |
WA |
1 ms |
2304 KB |
10_small-rand_7 |
WA |
1 ms |
2304 KB |
10_small-rand_8 |
WA |
1 ms |
2304 KB |
10_small-rand_9 |
AC |
1 ms |
2304 KB |
20_large-rand_0 |
WA |
71 ms |
7296 KB |
20_large-rand_1 |
WA |
76 ms |
7296 KB |
20_large-rand_2 |
WA |
70 ms |
7296 KB |
20_large-rand_3 |
WA |
78 ms |
7424 KB |
20_large-rand_4 |
WA |
74 ms |
7296 KB |
20_large-rand_5 |
WA |
94 ms |
7552 KB |
20_large-rand_6 |
WA |
91 ms |
7552 KB |
20_large-rand_7 |
WA |
74 ms |
7296 KB |
20_large-rand_8 |
WA |
80 ms |
7296 KB |
20_large-rand_9 |
WA |
65 ms |
7296 KB |
50_smallval-rand_0 |
WA |
87 ms |
6912 KB |
50_smallval-rand_1 |
WA |
73 ms |
6912 KB |
50_smallval-rand_10 |
WA |
70 ms |
6784 KB |
50_smallval-rand_11 |
WA |
83 ms |
6912 KB |
50_smallval-rand_12 |
WA |
62 ms |
6784 KB |
50_smallval-rand_13 |
WA |
78 ms |
6912 KB |
50_smallval-rand_14 |
WA |
82 ms |
6912 KB |
50_smallval-rand_15 |
WA |
83 ms |
6912 KB |
50_smallval-rand_16 |
WA |
74 ms |
6912 KB |
50_smallval-rand_17 |
WA |
75 ms |
6912 KB |
50_smallval-rand_18 |
WA |
75 ms |
6912 KB |
50_smallval-rand_19 |
WA |
77 ms |
6912 KB |
50_smallval-rand_2 |
WA |
83 ms |
6912 KB |
50_smallval-rand_3 |
WA |
76 ms |
6912 KB |
50_smallval-rand_4 |
WA |
84 ms |
6912 KB |
50_smallval-rand_5 |
WA |
86 ms |
6912 KB |
50_smallval-rand_6 |
WA |
65 ms |
6784 KB |
50_smallval-rand_7 |
WA |
70 ms |
6912 KB |
50_smallval-rand_8 |
WA |
88 ms |
6912 KB |
50_smallval-rand_9 |
WA |
77 ms |
6912 KB |
60_smallpart-rand_0 |
AC |
60 ms |
6784 KB |
60_smallpart-rand_1 |
AC |
60 ms |
6784 KB |
60_smallpart-rand_2 |
AC |
65 ms |
6784 KB |
60_smallpart-rand_3 |
AC |
62 ms |
6784 KB |
60_smallpart-rand_4 |
AC |
55 ms |
6784 KB |
60_smallpart-rand_5 |
AC |
54 ms |
6784 KB |
60_smallpart-rand_6 |
AC |
61 ms |
6784 KB |
60_smallpart-rand_7 |
AC |
65 ms |
6784 KB |
60_smallpart-rand_8 |
WA |
66 ms |
6784 KB |
60_smallpart-rand_9 |
AC |
61 ms |
6784 KB |
70_smallpart-rand_0 |
AC |
59 ms |
6528 KB |