Submission #68275

ソースコード

?
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
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
#include <bits/stdc++.h>
#define lol long long
using namespace std;
struct Segment
{
int n;
vector<lol> dat;
vector<int> mem;
vector<int> meml;
vector<int> memr;
Segment(int size){
n = 1;
while(size>n){
n *= 2;
}
dat.resize(n*2, 0);
mem.resize(n*2, 0);
meml.resize(n*2, 0);
memr.resize(n*2, 0);
return;
}
void set(int i, lol x){dat[i+n-1]=x;}
void build(){
for(int k=n-2;k>=0;k--) dat[k]=dat[2*k+1]+dat[2*k+2];
return;
}
void update(int a, int b, int y, vector<lol>& p){
update(a,b, 0, 0, n, p, y);
}
void update(int a, int b, int k, int l, int r, vector<lol>& p, int y){
eval(k, p);
if(a<=l && r<=b){
mem[k] = 1;
meml[k] = y+l-a;
memr[k] = y+l-a + r-l ;
eval(k, p);
}else if(a < r && l < b){
update(a, b, k*2+1, l, (l+r)/2, p, y);
update(a, b, k*2+2, (l+r)/2, r, p, y);
dat[k] = dat[2*k+1]+dat[2*k+2];
}
}
void eval(int k, vector<lol>& p){
if(mem[k]==0) return;
if(k < n-1){
mem[k*2+1] = 1;
meml[k*2+1] = meml[k];
memr[k*2+1] = (meml[k]+memr[k])/2;
mem[k*2+2] = 1;
meml[k*2+2] = (meml[k]+memr[k])/2;
memr[k*2+2] = memr[k];
}
//dat[k] = p.query(meml[k], memr[k], p);
dat[k] = p[memr[k]] - p[meml[k]];
mem[k] = 0;
}
lol query(int a,int b, vector<lol>& p){
return(query(a, b, 0, 0, n, p));
}
lol query(int a,int b, int k, int l, int r, vector<lol>& p){
eval(k, p);
if(r<=a||b<=l) return(0);
else if(a<=l&&r<=b) return(dat[k]);
else{
return(query(a,b,2*k+1,l,(l+r)/2, p) + query(a,b,2*k+2,(l+r)/2, r, p));
}
}
};
signed main(){
cin.tie(0);
ios::sync_with_stdio(false);
int n,m;
cin>>n>>m;
vector<lol> a(n),b(n+1,0);
for(int i=0;i<n;i++) cin >>a[i];
for(int i=1;i<=n;i++){
cin >>b[i];
b[i] += b[i-1];
}
Segment A(n);
for(int i=0;i<n;i++){
A.set(i, a[i]);
}
A.build();
while(m--){
int op,x,y,z;
int p,q;
cin >>op;
if(op){
cin >>p>>q;
p--,q--;
cout <<A.query(p,q+1, b)<<'\n';
}else{
cin >>x>>y>>z;
x--,y--;
A.update(x,x+z,y, b);
/*
for(int i=0;i<n;i++){
cout <<A.query(i,i+1,b)<<' ';
}cout <<'\n';*/
}
}
return(0);
}

ステータス

項目 データ
問題 1446 - Copy&Sum
ユーザー名 保守性不在
投稿日時 2021-09-03 19:06:00
言語 C++17
状態 Accepted
得点 12
ソースコード長 2767 Byte
最大実行時間 362 ms
最大メモリ使用量 21956 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in1 AC 27 ms 476 KB
1
in2 AC 21 ms 580 KB
1
in3 AC 30 ms 8652 KB
1
in4 AC 19 ms 8608 KB
1
in5 AC 24 ms 8564 KB
1
in6 AC 20 ms 8644 KB
1
in7 AC 21 ms 8596 KB
1
in8 AC 20 ms 8680 KB
1
in9 AC 19 ms 8636 KB
1
in10 AC 20 ms 564 KB
1
in11 AC 24 ms 652 KB
1
in12 AC 22 ms 604 KB
1
in13 AC 16 ms 680 KB
1
in14 AC 21 ms 628 KB
1
in15 AC 23 ms 576 KB
1
in16 AC 14 ms 396 KB
1
in17 AC 18 ms 472 KB
1
in18 AC 20 ms 520 KB
1
in19 AC 25 ms 540 KB
1
in20 AC 24 ms 532 KB
1
in21 AC 255 ms 14760 KB
1
in22 AC 265 ms 16304 KB
1
in23 AC 362 ms 17844 KB
1
in24 AC 326 ms 19384 KB
1
in25 AC 170 ms 20668 KB
1
in26 AC 174 ms 21956 KB
1