Submission #71985

ソースコード

?
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
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef unsigned long long int ull;
#define BIG_NUM 2000000000
#define HUGE_NUM 4000000000000000000 //オーバーフローに注意
#define MOD 1000000007
#define EPS 0.000000001
#define SIZE 300005
enum DIR{
North,
West,
South,
East,
};
struct NA{
NA(){
for(int i = 0; i < 4; i++){
value[i] = 0;
}
}
NA(ll arg_value[4]){
for(int i = 0; i < 4; i++){
value[i] = arg_value[i];
}
}
ll value[4];
};
int N = 1;
int table[6*SIZE];
NA ans[6*SIZE];
void init(int first_N){
while(N < first_N)N *= 2;
}
void first_add(int loc){
loc += N-1;
ans[loc].value[North] = 1;
if(N == 1)return;
int parent = (loc-1)/2;
while(true){
ans[parent].value[North] = ans[2*parent+1].value[North]+ans[2*parent+2].value[North];
if(parent == 0)break;
else{
parent = (parent-1)/2;
}
}
}
void update(int update_left,int update_right,ll move,int node_id,int node_left,int node_right){
if(update_right < node_left || update_left > node_right)return;
if(update_left <= node_left && update_right >= node_right){
int work[4];
for(int i = 0; i < 4; i++){
work[(i+move)%4] = ans[node_id].value[i];
}
for(int i = 0; i < 4; i++){
ans[node_id].value[i] = work[i];
}
table[node_id] += move;
return;
}else{
if(table[node_id] > 0){ //蓄積分
update(node_left,node_right,table[node_id],2*node_id+1,node_left,(node_left+node_right)/2);
update(node_left,node_right,table[node_id],2*node_id+2,(node_left+node_right)/2+1,node_right);
table[node_id] = 0;
}
int L = 2*node_id+1,R = 2*node_id+2;
update(update_left,update_right,move,2*node_id+1,node_left,(node_left+node_right)/2);
update(update_left,update_right,move,2*node_id+2,(node_left+node_right)/2+1,node_right);
//個数を再計算
for(int i = 0; i < 4; i++){
ans[node_id].value[i] = ans[L].value[i]+ans[R].value[i];
}
}
}
vector<int> query(int search_left,int search_right,int node_id,int node_left,int node_right){
vector<int> ret;
if(search_right < node_left || search_left > node_right){
for(int i = 0; i < 4; i++){
ret.push_back(0);
}
return ret;
}
if(search_left <= node_left && search_right >= node_right){
for(int i = 0; i < 4; i++){
ret.push_back(ans[node_id].value[i]);
}
return ret;
}else{
if(table[node_id] > 0){ //蓄積分
update(node_left,node_right,table[node_id],2*node_id+1,node_left,(node_left+node_right)/2);
update(node_left,node_right,table[node_id],2*node_id+2,(node_left+node_right)/2+1,node_right);
table[node_id] = 0;
}
vector<int> vec_L = query(search_left,search_right,2*node_id+1,node_left,(node_left+node_right)/2);
vector<int> vec_R = query(search_left,search_right,2*node_id+2,(node_left+node_right)/2+1,node_right);
for(int i = 0; i < 4; i++){
ret.push_back(vec_L[i]+vec_R[i]);
}
return ret;
}
}
int main(){
int first_N,Q;
scanf("%d %d",&first_N,&Q);
init(first_N);
//printf("N:%d\n",N);
for(int i = 0; i <= 2*N-2; i++){
for(int a = 0; a < 4; a++){
ans[i].value[a] = 0;
}
}
for(int i = 0; i < first_N; i++){
first_add(i);
}
int command;
int left,right;
int move;
for(int i = 0; i < Q; i++){
scanf("%d %d %d",&command,&left,&right);
left--;
right--;
if(command == 1){ //回転命令
scanf("%d",&move);
if(move < 0){
move = -((abs(move)%4));
move += 4;
move %= 4;
}else{
move %= 4;
}
if(move == 0)continue;
update(left,right,move,0,0,N-1);
}else{ //出力命令
vector<int> ret = query(left,right,0,0,N-1);
int to_N = ret[North];
int to_S = ret[South];
printf("%d\n",to_N-to_S);
}
}
return 0;
}

ステータス

項目 データ
問題 1545 - 回転マスゲーム
ユーザー名 syoribu
投稿日時 2022-08-30 09:55:57
言語 C++17
状態 Accepted
得点 10
ソースコード長 3941 Byte
最大実行時間 631 ms
最大メモリ使用量 62884 KB

セット

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

テストケース

ファイル名 状態 実行時間 メモリ使用量 #
in1 AC 36 ms 57948 KB
1
in2 AC 30 ms 58288 KB
1
in3 AC 28 ms 58900 KB
1
in4 AC 27 ms 58884 KB
1
in5 AC 31 ms 58860 KB
1
in6 AC 31 ms 58972 KB
1
in7 AC 28 ms 58824 KB
1
in8 AC 28 ms 58936 KB
1
in9 AC 31 ms 58792 KB
1
in10 AC 26 ms 58060 KB
1
in11 AC 26 ms 57920 KB
1
in12 AC 25 ms 58032 KB
1
in13 AC 25 ms 57888 KB
1
in14 AC 29 ms 57748 KB
1
in15 AC 36 ms 57860 KB
1
in16 AC 66 ms 57844 KB
1
in17 AC 461 ms 62184 KB
1
in18 AC 391 ms 62420 KB
1
in19 AC 150 ms 62400 KB
1
in20 AC 631 ms 62884 KB
1