oj.uz

Submission #427424

# Submission time Handle Problem Language Result Execution time Memory
427424 2021-06-14T15:07:29 Z arayi Game (IOI13_game) C++17
80 / 100
 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);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory 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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory 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

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory 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

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory 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

Subtask #5
0 / 20.0

# Verdict Execution time Memory 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 -