# |
제출 시각 |
아이디 |
문제 |
언어 |
결과 |
실행 시간 |
메모리 |
427424 |
2021-06-14T15:07:29 Z |
arayi |
게임 (IOI13_game) |
C++17 |
|
6463 ms |
256004 KB |
#include "game.h"
#include <bits/stdc++.h>
#define lli long long
#define ad push_back
using namespace std;
const int N = 1e6 + 30;
const int mod = 1e9;
long long gcd2(long long X, long long Y) {
while (X != Y && Y != 0) {
X %= Y; swap(X, Y);
}
return X;
}
int n, m, ii;
int l[N], r[N];
vector <int> e1;
vector <lli> e2;
vector<int> l1[N], r1[N];
vector<lli> t[N];
map <pair<int, int>, lli> mp;
lli qry1(int l, int r, int nd, int nl = 0, int nr = m - 1, int i1 = 0)
{
if(l > nr || r < nl || i1 == mod) return 0;
if(l == nl && r == nr) return t[nd][i1];
int mid = (nl + nr) / 2;
return gcd2(qry1(l, min(mid, r), nd, nl, mid, l1[nd][i1]),
qry1(max(mid + 1, l), r, nd, mid + 1, nr, r1[nd][i1]));
}
lli qry(int l, int r, int l1, int r1, int nl = 0, int nr = n - 1, int nd = 0)
{
if(l > nr || r < nl || nd == mod) return 0;
if(l == nl && r == nr) return qry1(l1, r1, nd);
int mid = (nl + nr) / 2;
return gcd2(qry(l, min(mid, r), l1, r1, nl, mid, ::l[nd]),
qry(max(mid + 1, l), r, l1, r1, mid + 1, nr, ::r[nd]));
}
void push1(int nd, int i)
{
if(i < 0) l1[nd][-i-1]=l1[nd].size();
else r1[nd][i-1]=l1[nd].size();
l1[nd].ad(mod);
r1[nd].ad(mod);
t[nd].ad(0);
}
void upd1(int l1, int r1, int R, int c, lli v, int nd, int l = 0, int r = m - 1, int i1 = 0, int par = 0)
{
if(l > c || r < c) return;
if(i1 == mod) i1 = ::l1[nd].size(), push1(nd, par);
if(l == r)
{
if(mp[make_pair(R, c)] == 0)
{
t[nd][i1] = gcd2(t[nd][i1], v);
return;
}
t[nd][i1] = v;
if(l1 < R) t[nd][i1] = gcd2(t[nd][i1], qry(l1, R - 1, l, l));
if(r1 > R) t[nd][i1] = gcd2(t[nd][i1], qry(R + 1, r1, l, l));
return;
}
int mid = (l + r) / 2;
upd1(l1, r1, R, c, v, nd, l, mid, ::l1[nd][i1], -i1-1);
upd1(l1, r1, R, c, v, nd, mid + 1, r, ::r1[nd][i1], i1+1);
t[nd][i1] = 0;
if(::l1[nd][i1]!= mod) t[nd][i1] = t[nd][::l1[nd][i1]];
if(::r1[nd][i1]!= mod) t[nd][i1] = gcd2(t[nd][i1], t[nd][::r1[nd][i1]]);
}
void push(int i)
{
if(i < 0) l[-i-1]=ii;
else r[i-1]=ii;
l[ii]=r[ii]=mod;
l1[ii]=r1[ii]=e1;
t[ii++]=e2;
}
void upd(int r1, int c, lli v, int l = 0, int r = n - 1, int nd = 0, int par = 0)
{
if(l > r1 || r < r1) return;
if(nd == mod) nd = ii, push(par);
upd1(l, r, r1, c, v, nd);
if(l==r) return;
int mid = (l + r) / 2;
upd(r1, c, v, l, mid, ::l[nd], -nd-1);
upd(r1, c, v, mid + 1, r, ::r[nd], nd+1);
}
void init(int R, int C)
{
n = R, m = C;
ii++;
e1.ad(mod), e2.ad(0);
l[0] = r[0] = mod;
l1[0] = r1[0] = e1;
t[0] = e2;
}
void update(int P, int Q, long long K)
{
upd(P, Q, K);
mp[make_pair(P, Q)]=K;
}
long long calculate(int P, int Q, int U, int V) {
return qry(P, U, Q, V);
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
45 ms |
70732 KB |
Output is correct |
2 |
Correct |
49 ms |
70852 KB |
Output is correct |
3 |
Correct |
41 ms |
70756 KB |
Output is correct |
4 |
Correct |
41 ms |
70640 KB |
Output is correct |
5 |
Correct |
40 ms |
70732 KB |
Output is correct |
6 |
Correct |
42 ms |
70836 KB |
Output is correct |
7 |
Correct |
40 ms |
70744 KB |
Output is correct |
8 |
Correct |
40 ms |
70640 KB |
Output is correct |
9 |
Correct |
40 ms |
70720 KB |
Output is correct |
10 |
Correct |
40 ms |
70704 KB |
Output is correct |
11 |
Correct |
42 ms |
70728 KB |
Output is correct |
12 |
Correct |
41 ms |
70692 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
39 ms |
70648 KB |
Output is correct |
2 |
Correct |
42 ms |
70732 KB |
Output is correct |
3 |
Correct |
41 ms |
70660 KB |
Output is correct |
4 |
Correct |
754 ms |
83576 KB |
Output is correct |
5 |
Correct |
606 ms |
83768 KB |
Output is correct |
6 |
Correct |
601 ms |
80184 KB |
Output is correct |
7 |
Correct |
699 ms |
80080 KB |
Output is correct |
8 |
Correct |
464 ms |
78552 KB |
Output is correct |
9 |
Correct |
662 ms |
80272 KB |
Output is correct |
10 |
Correct |
651 ms |
79384 KB |
Output is correct |
11 |
Correct |
41 ms |
70688 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
40 ms |
70744 KB |
Output is correct |
2 |
Correct |
44 ms |
70824 KB |
Output is correct |
3 |
Correct |
49 ms |
70732 KB |
Output is correct |
4 |
Correct |
41 ms |
70664 KB |
Output is correct |
5 |
Correct |
43 ms |
70728 KB |
Output is correct |
6 |
Correct |
41 ms |
70724 KB |
Output is correct |
7 |
Correct |
40 ms |
70728 KB |
Output is correct |
8 |
Correct |
42 ms |
70724 KB |
Output is correct |
9 |
Correct |
41 ms |
70736 KB |
Output is correct |
10 |
Correct |
47 ms |
70744 KB |
Output is correct |
11 |
Correct |
42 ms |
70724 KB |
Output is correct |
12 |
Correct |
1307 ms |
86512 KB |
Output is correct |
13 |
Correct |
1945 ms |
78204 KB |
Output is correct |
14 |
Correct |
502 ms |
74032 KB |
Output is correct |
15 |
Correct |
2345 ms |
80056 KB |
Output is correct |
16 |
Correct |
298 ms |
87280 KB |
Output is correct |
17 |
Correct |
1018 ms |
82164 KB |
Output is correct |
18 |
Correct |
1697 ms |
87640 KB |
Output is correct |
19 |
Correct |
1538 ms |
87656 KB |
Output is correct |
20 |
Correct |
1416 ms |
87028 KB |
Output is correct |
21 |
Correct |
39 ms |
70724 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
42 ms |
70744 KB |
Output is correct |
2 |
Correct |
46 ms |
70768 KB |
Output is correct |
3 |
Correct |
42 ms |
70780 KB |
Output is correct |
4 |
Correct |
44 ms |
70780 KB |
Output is correct |
5 |
Correct |
41 ms |
70732 KB |
Output is correct |
6 |
Correct |
42 ms |
70832 KB |
Output is correct |
7 |
Correct |
42 ms |
70696 KB |
Output is correct |
8 |
Correct |
39 ms |
70724 KB |
Output is correct |
9 |
Correct |
39 ms |
70744 KB |
Output is correct |
10 |
Correct |
40 ms |
70856 KB |
Output is correct |
11 |
Correct |
41 ms |
70704 KB |
Output is correct |
12 |
Correct |
781 ms |
83764 KB |
Output is correct |
13 |
Correct |
600 ms |
83832 KB |
Output is correct |
14 |
Correct |
606 ms |
80180 KB |
Output is correct |
15 |
Correct |
687 ms |
80088 KB |
Output is correct |
16 |
Correct |
477 ms |
78556 KB |
Output is correct |
17 |
Correct |
668 ms |
80252 KB |
Output is correct |
18 |
Correct |
585 ms |
79268 KB |
Output is correct |
19 |
Correct |
1288 ms |
86508 KB |
Output is correct |
20 |
Correct |
1926 ms |
78196 KB |
Output is correct |
21 |
Correct |
523 ms |
74092 KB |
Output is correct |
22 |
Correct |
2271 ms |
80076 KB |
Output is correct |
23 |
Correct |
367 ms |
87152 KB |
Output is correct |
24 |
Correct |
1122 ms |
82156 KB |
Output is correct |
25 |
Correct |
1826 ms |
87492 KB |
Output is correct |
26 |
Correct |
1622 ms |
87576 KB |
Output is correct |
27 |
Correct |
1483 ms |
87036 KB |
Output is correct |
28 |
Correct |
1403 ms |
223300 KB |
Output is correct |
29 |
Correct |
2850 ms |
237736 KB |
Output is correct |
30 |
Correct |
6390 ms |
193088 KB |
Output is correct |
31 |
Correct |
6227 ms |
169832 KB |
Output is correct |
32 |
Correct |
1741 ms |
75140 KB |
Output is correct |
33 |
Correct |
1675 ms |
77768 KB |
Output is correct |
34 |
Correct |
1000 ms |
235244 KB |
Output is correct |
35 |
Correct |
2385 ms |
156012 KB |
Output is correct |
36 |
Correct |
4103 ms |
235296 KB |
Output is correct |
37 |
Correct |
3360 ms |
235308 KB |
Output is correct |
38 |
Correct |
3176 ms |
234752 KB |
Output is correct |
39 |
Correct |
2731 ms |
198648 KB |
Output is correct |
40 |
Correct |
44 ms |
70724 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
42 ms |
70744 KB |
Output is correct |
2 |
Correct |
44 ms |
70764 KB |
Output is correct |
3 |
Correct |
44 ms |
70728 KB |
Output is correct |
4 |
Correct |
41 ms |
70732 KB |
Output is correct |
5 |
Correct |
49 ms |
70716 KB |
Output is correct |
6 |
Correct |
42 ms |
70792 KB |
Output is correct |
7 |
Correct |
40 ms |
70708 KB |
Output is correct |
8 |
Correct |
41 ms |
70748 KB |
Output is correct |
9 |
Correct |
42 ms |
70732 KB |
Output is correct |
10 |
Correct |
45 ms |
70784 KB |
Output is correct |
11 |
Correct |
41 ms |
70784 KB |
Output is correct |
12 |
Correct |
819 ms |
83660 KB |
Output is correct |
13 |
Correct |
573 ms |
83932 KB |
Output is correct |
14 |
Correct |
580 ms |
80264 KB |
Output is correct |
15 |
Correct |
647 ms |
79968 KB |
Output is correct |
16 |
Correct |
479 ms |
78588 KB |
Output is correct |
17 |
Correct |
642 ms |
80168 KB |
Output is correct |
18 |
Correct |
633 ms |
79296 KB |
Output is correct |
19 |
Correct |
1280 ms |
86608 KB |
Output is correct |
20 |
Correct |
1994 ms |
78156 KB |
Output is correct |
21 |
Correct |
504 ms |
74064 KB |
Output is correct |
22 |
Correct |
2264 ms |
80076 KB |
Output is correct |
23 |
Correct |
323 ms |
87236 KB |
Output is correct |
24 |
Correct |
1008 ms |
82124 KB |
Output is correct |
25 |
Correct |
1598 ms |
87584 KB |
Output is correct |
26 |
Correct |
1460 ms |
87652 KB |
Output is correct |
27 |
Correct |
1425 ms |
87020 KB |
Output is correct |
28 |
Correct |
1422 ms |
223332 KB |
Output is correct |
29 |
Correct |
2760 ms |
237672 KB |
Output is correct |
30 |
Correct |
6463 ms |
193288 KB |
Output is correct |
31 |
Correct |
6243 ms |
169904 KB |
Output is correct |
32 |
Correct |
1662 ms |
75320 KB |
Output is correct |
33 |
Correct |
1676 ms |
77620 KB |
Output is correct |
34 |
Correct |
995 ms |
235452 KB |
Output is correct |
35 |
Correct |
1871 ms |
156032 KB |
Output is correct |
36 |
Correct |
3875 ms |
235204 KB |
Output is correct |
37 |
Correct |
3205 ms |
235272 KB |
Output is correct |
38 |
Correct |
3201 ms |
234684 KB |
Output is correct |
39 |
Runtime error |
1031 ms |
256004 KB |
Execution killed with signal 9 |
40 |
Halted |
0 ms |
0 KB |
- |