#include <bits/stdc++.h>
#include "game.h"
#define pb push_back
//#define DEBUGGING
void __print(int i) { std::cerr << i; }
void __print(long long int i) { std::cerr << i; }
void __print(const char *c) { std::cerr << c; }
template<typename T>
void __print(T& t) { std::cerr <<"{";int f = 0; for (auto& i : t) { std::cerr << ((f++) ? ", ": ""); __print(i); } std::cerr << "}"; }
void _print() { std::cerr << "]\n"; }
template<typename T, typename... V>
void _print(T t, V... v) { __print(t); if (sizeof...(v)) std::cerr << ", "; _print(v...); }
#ifdef DEBUGGING
#define debug(x...) std::cerr << "[" << (#x) << "] = ["; _print(x)
#else
#define debug(x...)
#endif
long long gcd(long long X, long long Y) {
long long tmp;
while (X != Y && Y != 0) {
tmp = X;
X = Y;
Y = tmp % Y;
}
return X;
}
struct SegTree1D
{
std::vector<int> up, down;
std::vector<long long> data;
SegTree1D() : up(1, -1), down(1, -1), data(1, 0) {}
void push(int u, int d, int index)
{
if (d - u == 1)
return;
if (up[index] == -1)
{
up[index] = data.size();
up.pb(-1);
down.pb(-1);
data.pb(0);
}
if (down[index] == -1)
{
down[index] = data.size();
up.pb(-1);
down.pb(-1);
data.pb(0);
}
}
void set(int u, int d, int index, int y, long long val)
{
debug(u, d, index, y, val);
if (y >= d || u > y)
return;
push(u, d, index);
if (u + 1 == d)
{
data[index] = val;
return;
}
int m = u+d>>1;
set(u, m, up[index], y, val);
set(m, d, down[index], y, val);
data[index] = gcd(data[up[index]], data[down[index]]);
}
long long int get(int u, int d, int index, int uu, int dd)
{
if (uu >= d || u >= dd || index == -1)
return 0;
if (dd >= d && u >= uu)
return data[index];
int m = u+d>>1;
long long ures = get(u, m, up[index], uu, dd);
long long dres = get(m, d, down[index], uu, dd);
return gcd(ures, dres);
}
};
std::vector<SegTree1D> st;
std::map<int, int> sts;
int R, C;
struct SegTree2D
{
std::vector<int> up, down, root;
std::vector<int> left, right;
std::vector<long long> data;
SegTree2D() : up(1, -1), down(1, -1), root(1, -1) {}
void push_x(int l, int r, int index)
{
if (r - l == 1)
return;
if (left[index] == -1)
{
left[index] = data.size();
left.pb(-1);
right.pb(-1);
data.pb(0);
}
if (right[index] == -1)
{
right[index] = data.size();
left.pb(-1);
right.pb(-1);
data.pb(0);
}
}
void push_y(int u, int d, int index)
{
if (up[index] == -1 && d - u > 1)
{
up[index] = root.size();
up.pb(-1);
down.pb(-1);
root.pb(-1);
}
if (down[index] == -1 && d - u > 1)
{
down[index] = root.size();
up.pb(-1);
down.pb(-1);
root.pb(-1);
}
if (root[index] == -1)
{
root[index] = data.size();
left.pb(-1);
right.pb(-1);
data.pb(0);
}
}
long long int query1d(int l, int r, int index, int ll, int rr)
{
if (index == -1 || ll >= r || l >= rr)
return 0;
if (rr >= r && l >= ll)
return data[index];
int m = l+r>>1;
long long int lres = query1d(l, m, left[index], ll, rr);
long long int rres = query1d(m, r, right[index], ll, rr);
return gcd(lres, rres);
}
long long int query2d(int u, int d, int index, int uu, int dd, int ll, int rr)
{
if (index == -1 || uu >= d || u >= dd)
return 0;
if (dd >= d && u >= uu)
return query1d(0, C, root[index], ll, rr);
int m = u+d>>1;
long long int ures = query2d(u, m, up[index], uu, dd, ll, rr);
long long int dres = query2d(m, d, down[index], uu, dd, ll, rr);
return gcd(ures, dres);
}
void update1d(int l, int r, int index, int x, long long int val)
{
if (x >= r || l > x)
return;
push_x(l, r, index);
if (l + 1 == r)
{
data[index] = val;
return;
}
int m = l+r>>1;
update1d(l, m, left[index], x, val);
update1d(m, r, right[index], x, val);
data[index] = gcd(data[left[index]], data[right[index]]);
}
void update2d(int u, int d, int index, int y, int x)
{
if (y >= d || u > y)
return;
push_y(u, d, index);
update1d(0, C, root[index], x, st[sts[x]].get(0, R, 0, u, d));
debug(u, d, y, x, root[index], x, st[sts[x]].get(0, R, 0, u, d));
if (u + 1 == d)
return;
int m = u+d>>1;
update2d(u, m, up[index], y, x);
update2d(m, d, down[index], y, x);
}
};
SegTree2D st2;
void init(int r, int c)
{
R = r;
C = c;
}
void update(int P, int Q, long long int K)
{
if (sts.find(Q) == sts.end())
{
sts[Q] = st.size();
st.pb(SegTree1D());
}
st[sts[Q]].set(0, R, 0, P, K);
st2.update2d(0, R, 0, P, Q);
}
long long int calculate(int P, int Q, int U, int V)
{
return st2.query2d(0, R, 0, P, U+1, Q, V+1);
}
Compilation message
game.cpp: In member function 'void SegTree1D::set(int, int, int, int, long long int)':
game.cpp:69:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
69 | int m = u+d>>1;
| ~^~
game.cpp: In member function 'long long int SegTree1D::get(int, int, int, int, int)':
game.cpp:80:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
80 | int m = u+d>>1;
| ~^~
game.cpp: In member function 'long long int SegTree2D::query1d(int, int, int, int, int)':
game.cpp:146:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
146 | int m = l+r>>1;
| ~^~
game.cpp: In member function 'long long int SegTree2D::query2d(int, int, int, int, int, int, int)':
game.cpp:158:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
158 | int m = u+d>>1;
| ~^~
game.cpp: In member function 'void SegTree2D::update1d(int, int, int, int, long long int)':
game.cpp:174:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
174 | int m = l+r>>1;
| ~^~
game.cpp: In member function 'void SegTree2D::update2d(int, int, int, int, int)':
game.cpp:189:26: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
189 | int m = u+d>>1;
| ~^~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
300 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
296 KB |
Output is correct |
8 |
Correct |
1 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
300 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
1 ms |
212 KB |
Output is correct |
4 |
Correct |
453 ms |
19140 KB |
Output is correct |
5 |
Correct |
270 ms |
19000 KB |
Output is correct |
6 |
Correct |
358 ms |
16620 KB |
Output is correct |
7 |
Correct |
380 ms |
16340 KB |
Output is correct |
8 |
Correct |
265 ms |
13984 KB |
Output is correct |
9 |
Correct |
375 ms |
16460 KB |
Output is correct |
10 |
Correct |
345 ms |
16032 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
296 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
304 KB |
Output is correct |
9 |
Correct |
1 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
631 ms |
23288 KB |
Output is correct |
13 |
Correct |
988 ms |
10608 KB |
Output is correct |
14 |
Correct |
234 ms |
5656 KB |
Output is correct |
15 |
Correct |
1161 ms |
13776 KB |
Output is correct |
16 |
Correct |
172 ms |
23892 KB |
Output is correct |
17 |
Correct |
566 ms |
21172 KB |
Output is correct |
18 |
Correct |
952 ms |
25384 KB |
Output is correct |
19 |
Correct |
801 ms |
25520 KB |
Output is correct |
20 |
Correct |
759 ms |
24920 KB |
Output is correct |
21 |
Correct |
1 ms |
340 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
468 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
300 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
1 ms |
428 KB |
Output is correct |
10 |
Correct |
1 ms |
296 KB |
Output is correct |
11 |
Correct |
1 ms |
340 KB |
Output is correct |
12 |
Correct |
412 ms |
19104 KB |
Output is correct |
13 |
Correct |
267 ms |
19020 KB |
Output is correct |
14 |
Correct |
350 ms |
16724 KB |
Output is correct |
15 |
Correct |
391 ms |
16248 KB |
Output is correct |
16 |
Correct |
261 ms |
14004 KB |
Output is correct |
17 |
Correct |
377 ms |
16472 KB |
Output is correct |
18 |
Correct |
354 ms |
16152 KB |
Output is correct |
19 |
Correct |
612 ms |
23232 KB |
Output is correct |
20 |
Correct |
981 ms |
10684 KB |
Output is correct |
21 |
Correct |
233 ms |
5704 KB |
Output is correct |
22 |
Correct |
1177 ms |
13660 KB |
Output is correct |
23 |
Correct |
170 ms |
23960 KB |
Output is correct |
24 |
Correct |
577 ms |
21220 KB |
Output is correct |
25 |
Correct |
873 ms |
25396 KB |
Output is correct |
26 |
Correct |
788 ms |
25504 KB |
Output is correct |
27 |
Correct |
755 ms |
24928 KB |
Output is correct |
28 |
Correct |
925 ms |
256000 KB |
Output is correct |
29 |
Runtime error |
1562 ms |
256000 KB |
Execution killed with signal 9 |
30 |
Halted |
0 ms |
0 KB |
- |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
2 ms |
424 KB |
Output is correct |
3 |
Correct |
1 ms |
468 KB |
Output is correct |
4 |
Correct |
1 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
212 KB |
Output is correct |
6 |
Correct |
1 ms |
468 KB |
Output is correct |
7 |
Correct |
1 ms |
212 KB |
Output is correct |
8 |
Correct |
1 ms |
300 KB |
Output is correct |
9 |
Correct |
1 ms |
468 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
296 KB |
Output is correct |
12 |
Correct |
412 ms |
19160 KB |
Output is correct |
13 |
Correct |
289 ms |
19044 KB |
Output is correct |
14 |
Correct |
342 ms |
16540 KB |
Output is correct |
15 |
Correct |
389 ms |
16444 KB |
Output is correct |
16 |
Correct |
265 ms |
14012 KB |
Output is correct |
17 |
Correct |
365 ms |
16488 KB |
Output is correct |
18 |
Correct |
340 ms |
16084 KB |
Output is correct |
19 |
Correct |
617 ms |
23284 KB |
Output is correct |
20 |
Correct |
972 ms |
10612 KB |
Output is correct |
21 |
Correct |
236 ms |
5608 KB |
Output is correct |
22 |
Correct |
1223 ms |
13708 KB |
Output is correct |
23 |
Correct |
173 ms |
23900 KB |
Output is correct |
24 |
Correct |
585 ms |
21220 KB |
Output is correct |
25 |
Correct |
969 ms |
25344 KB |
Output is correct |
26 |
Correct |
910 ms |
25588 KB |
Output is correct |
27 |
Correct |
855 ms |
24944 KB |
Output is correct |
28 |
Correct |
858 ms |
256000 KB |
Output is correct |
29 |
Runtime error |
1585 ms |
256000 KB |
Execution killed with signal 9 |
30 |
Halted |
0 ms |
0 KB |
- |