Submission #77424

ソースコード

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include <bits/stdc++.h>
using namespace std;
long long N, Q;
const long long INF = LONG_LONG_MAX;
struct LazySegmentTree {
private:
long long n;
vector<long long> node, lazy;
vector<bool> lazyFlag;
public:
LazySegmentTree(vector<long long> v) {
long long sz = (long long)v.size();
n = 1; while(n < sz) n *= 2;
node.resize(2*n-1);
lazy.resize(2*n-1, 0);
lazyFlag.resize(2*n-1, false);
for(long long i=0; i<sz; i++) node[i+n-1] = v[i];
for(long long i=n-2; i>=0; i--) node[i] = (node[i*2+1]+node[i*2+2]);
}
void lazyEvaluate(long long k, long long l, long long r) {
if(lazyFlag[k]) {
node[k] = lazy[k];
if(r - l > 1) {
lazy[k*2+1] = lazy[k*2+2] = lazy[k];
lazyFlag[k*2+1] = lazyFlag[k*2+2] = true;
}
lazyFlag[k] = false;
}
}
void update(long long a, long long b, long long x, long long k=0, long long l=0, long long r=-1) {
if(r < 0) r = n;
lazyEvaluate(k, l, r);
if(b <= l || r <= a) return;
if(a <= l && r <= b) {
lazy[k] = x;
lazyFlag[k] = true;
lazyEvaluate(k, l, r);
}
else {
update(a, b, x, 2*k+1, l, (l+r)/2);
update(a, b, x, 2*k+2, (l+r)/2, r);
node[k] = (node[2*k+1]+node[2*k+2]);
}
}
long long find(long long a, long long b, long long k=0, long long l=0, long long r=-1) {
if(r < 0) r = n;
lazyEvaluate(k, l, r);
if(b <= l || r <= a) return 0;
if(a <= l && r <= b) return node[k];
long long vl = find(a, b, 2*k+1, l, (l+r)/2);
long long vr = find(a, b, 2*k+2, (l+r)/2, r);
return (vl+vr);
}
};
int main() {
cin >> N >> Q;
LazySegmentTree seg( vector<long long>(N+1, 0) );
for(long long i=0; i<Q; i++) {
long long query; cin >> query;
if(query == 1) {
long long s, t, x; cin >> s >> t ;
//seg.update(s, t+1, x);
if(seg.find(s,t+1)==0){
seg.update(s,s+1,1);
}
}else {
long long s, t; cin >> s >> t;
seg.update(s,t+1,0);
}
cout<<seg.find(1,N+1)<<"\n";
}
return 0;
}

ステータス

項目 データ
問題 1724 - Machines
ユーザー名 ei2326
投稿日時 2023-12-21 17:07:14
言語 C++17
状態 Accepted
得点 5
ソースコード長 2385 Byte
最大実行時間 1006 ms
最大メモリ使用量 39596 KB

セット

セット 得点 Cases
1 ALL 5 / 5 *

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
00_sample_00.in AC 31 ms 604 KB
1
01_small_00.in AC 19 ms 452 KB
1
01_small_01.in AC 27 ms 552 KB
1
01_small_02.in AC 21 ms 524 KB
1
02_corner_minimum_00.in AC 26 ms 496 KB
1
02_corner_minimum_01.in AC 18 ms 464 KB
1
03_general_00.in AC 24 ms 560 KB
1
03_general_01.in AC 19 ms 400 KB
1
04_random_00.in AC 16 ms 496 KB
1
04_random_01.in AC 16 ms 588 KB
1
04_random_02.in AC 24 ms 552 KB
1
04_random_03.in AC 21 ms 520 KB
1
05_large_00.in AC 21 ms 744 KB
1
05_large_01.in AC 18 ms 692 KB
1
05_large_02.in AC 29 ms 880 KB
1
05_large_03.in AC 56 ms 1188 KB
1
06_corner_maximum_00.in AC 318 ms 5424 KB
1
06_corner_maximum_01.in AC 638 ms 10584 KB
1
06_corner_maximum_02.in AC 1006 ms 20184 KB
1
07_corner_critical_00.in AC 875 ms 20748 KB
1
07_corner_critical_01.in AC 888 ms 22584 KB
1
07_corner_critical_02.in AC 880 ms 24424 KB
1
07_corner_critical_03.in AC 825 ms 26656 KB
1
07_corner_critical_04.in AC 844 ms 28496 KB
1
07_corner_critical_05.in AC 886 ms 30344 KB
1
07_corner_critical_06.in AC 909 ms 32320 KB
1
07_corner_critical_07.in AC 839 ms 34288 KB
1
07_corner_critical_08.in AC 884 ms 34852 KB
1
07_corner_critical_09.in AC 871 ms 35676 KB
1
07_corner_critical_10.in AC 813 ms 36628 KB
1
07_corner_critical_11.in AC 871 ms 37196 KB
1
07_corner_critical_12.in AC 904 ms 37884 KB
1
07_corner_critical_13.in AC 1006 ms 39596 KB
1
07_corner_critical_14.in AC 654 ms 21860 KB
1