oj.uz

Submission #427428

# Submission time Handle Problem Language Result Execution time Memory
427428 2021-06-14T15:11:17 Z arayi Game (IOI13_game) C++17
80 / 100
 7297 ms 256004 KB 
#include "game.h"
#include <bits/stdc++.h>
#define lli long long
#define ad push_back
using namespace std;
const int N = 7e5 + 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 27 ms 49612 KB Output is correct
2 Correct 29 ms 49696 KB Output is correct
3 Correct 28 ms 49612 KB Output is correct
4 Correct 29 ms 49608 KB Output is correct
5 Correct 32 ms 49604 KB Output is correct
6 Correct 34 ms 49612 KB Output is correct
7 Correct 29 ms 49636 KB Output is correct
8 Correct 27 ms 49612 KB Output is correct
9 Correct 28 ms 49684 KB Output is correct
10 Correct 28 ms 49644 KB Output is correct
11 Correct 30 ms 49568 KB Output is correct
12 Correct 27 ms 49492 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 34 ms 49492 KB Output is correct
2 Correct 32 ms 49608 KB Output is correct
3 Correct 27 ms 49520 KB Output is correct
4 Correct 793 ms 59712 KB Output is correct
5 Correct 660 ms 59964 KB Output is correct
6 Correct 782 ms 56340 KB Output is correct
7 Correct 797 ms 56128 KB Output is correct
8 Correct 534 ms 54748 KB Output is correct
9 Correct 746 ms 56320 KB Output is correct
10 Correct 755 ms 55516 KB Output is correct
11 Correct 34 ms 49608 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 49576 KB Output is correct
2 Correct 33 ms 49612 KB Output is correct
3 Correct 36 ms 49616 KB Output is correct
4 Correct 34 ms 49556 KB Output is correct
5 Correct 31 ms 49508 KB Output is correct
6 Correct 39 ms 49600 KB Output is correct
7 Correct 32 ms 49620 KB Output is correct
8 Correct 32 ms 49640 KB Output is correct
9 Correct 32 ms 49708 KB Output is correct
10 Correct 35 ms 49644 KB Output is correct
11 Correct 30 ms 49632 KB Output is correct
12 Correct 1403 ms 62616 KB Output is correct
13 Correct 2111 ms 54296 KB Output is correct
14 Correct 534 ms 50152 KB Output is correct
15 Correct 3048 ms 56248 KB Output is correct
16 Correct 323 ms 63300 KB Output is correct
17 Correct 1090 ms 58312 KB Output is correct
18 Correct 1878 ms 63696 KB Output is correct
19 Correct 1540 ms 63832 KB Output is correct
20 Correct 1542 ms 63252 KB Output is correct
21 Correct 33 ms 49612 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 49496 KB Output is correct
2 Correct 30 ms 49676 KB Output is correct
3 Correct 31 ms 49724 KB Output is correct
4 Correct 28 ms 49604 KB Output is correct
5 Correct 30 ms 49624 KB Output is correct
6 Correct 30 ms 49636 KB Output is correct
7 Correct 30 ms 49580 KB Output is correct
8 Correct 33 ms 49588 KB Output is correct
9 Correct 31 ms 49604 KB Output is correct
10 Correct 31 ms 49632 KB Output is correct
11 Correct 32 ms 49744 KB Output is correct
12 Correct 808 ms 59756 KB Output is correct
13 Correct 630 ms 60080 KB Output is correct
14 Correct 832 ms 56324 KB Output is correct
15 Correct 947 ms 56112 KB Output is correct
16 Correct 602 ms 54724 KB Output is correct
17 Correct 887 ms 56240 KB Output is correct
18 Correct 759 ms 55504 KB Output is correct
19 Correct 1373 ms 62648 KB Output is correct
20 Correct 2244 ms 54312 KB Output is correct
21 Correct 606 ms 50248 KB Output is correct
22 Correct 2474 ms 56252 KB Output is correct
23 Correct 347 ms 63384 KB Output is correct
24 Correct 1130 ms 58252 KB Output is correct
25 Correct 2398 ms 63744 KB Output is correct
26 Correct 1894 ms 63836 KB Output is correct
27 Correct 1701 ms 63188 KB Output is correct
28 Correct 1587 ms 198676 KB Output is correct
29 Correct 3109 ms 212920 KB Output is correct
30 Correct 7297 ms 168700 KB Output is correct
31 Correct 7287 ms 145464 KB Output is correct
32 Correct 1806 ms 51124 KB Output is correct
33 Correct 1968 ms 53580 KB Output is correct
34 Correct 2222 ms 212164 KB Output is correct
35 Correct 3074 ms 133204 KB Output is correct
36 Correct 6382 ms 213120 KB Output is correct
37 Correct 4306 ms 213436 KB Output is correct
38 Correct 3850 ms 212864 KB Output is correct
39 Correct 3024 ms 176768 KB Output is correct
40 Correct 41 ms 49668 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 49612 KB Output is correct
2 Correct 42 ms 49608 KB Output is correct
3 Correct 46 ms 49608 KB Output is correct
4 Correct 35 ms 49596 KB Output is correct
5 Correct 46 ms 49572 KB Output is correct
6 Correct 36 ms 49700 KB Output is correct
7 Correct 36 ms 49556 KB Output is correct
8 Correct 35 ms 49588 KB Output is correct
9 Correct 38 ms 49612 KB Output is correct
10 Correct 38 ms 49648 KB Output is correct
11 Correct 36 ms 49648 KB Output is correct
12 Correct 921 ms 62756 KB Output is correct
13 Correct 644 ms 62728 KB Output is correct
14 Correct 687 ms 59308 KB Output is correct
15 Correct 788 ms 59168 KB Output is correct
16 Correct 575 ms 57612 KB Output is correct
17 Correct 846 ms 59244 KB Output is correct
18 Correct 755 ms 58396 KB Output is correct
19 Correct 1477 ms 65464 KB Output is correct
20 Correct 2232 ms 57144 KB Output is correct
21 Correct 530 ms 53716 KB Output is correct
22 Correct 2506 ms 59692 KB Output is correct
23 Correct 360 ms 66708 KB Output is correct
24 Correct 1136 ms 61968 KB Output is correct
25 Correct 1953 ms 67572 KB Output is correct
26 Correct 1609 ms 67672 KB Output is correct
27 Correct 1561 ms 67320 KB Output is correct
28 Correct 1611 ms 203076 KB Output is correct
29 Correct 3273 ms 218028 KB Output is correct
30 Correct 7144 ms 174084 KB Output is correct
31 Correct 6794 ms 151536 KB Output is correct
32 Correct 1802 ms 57488 KB Output is correct
33 Correct 1884 ms 59912 KB Output is correct
34 Correct 1210 ms 216744 KB Output is correct
35 Correct 2647 ms 138276 KB Output is correct
36 Correct 4856 ms 218000 KB Output is correct
37 Correct 4908 ms 218964 KB Output is correct
38 Correct 3905 ms 218744 KB Output is correct
39 Runtime error 1484 ms 256004 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -