oj.uz

Submission #919587

# Submission time Handle Problem Language Result Execution time Memory
919587 2024-02-01T07:53:31 Z Khanhcsp2 Game (IOI13_game) C++14
100 / 100
 3342 ms 66640 KB 
#include "game.h"
#include<bits/stdc++.h>
#define el '\n'
#define fi first
#define sc second
#define pii pair<int, int>
#define all(v) v.begin(), v.end()
using namespace std;
using ll=long long;
int m, n;
const int N = 5e6;
ll gcd(ll a, ll b)
{
    if (!b) return a;
    else return gcd(b, a % b);
}
ll ss[N];
int L[N], R[N], root[N], lazy[N];
int cur = 1;
void down(int id, int l, int r)
{
    int mid=(l+r)>>1;
    if(lazy[id]<=mid)
    {
        L[id] = ++cur;
        ss[L[id]] = ss[id];
        lazy[L[id]] = lazy[id];
    }
    else
    {
        R[id] = ++cur;
        ss[R[id]] = ss[id];
        lazy[R[id]] = lazy[id];
    }
    lazy[id] = 0;
}
void update1(int id, int l, int r, int pos, ll val)
{
    if(l==r)
    {
        ss[id]=val;
        return;
    }
    if(lazy[id])
    {
        if(lazy[id] == pos) ss[id] = val;
        else down(id, l, r);
    }
    int mid = (l+r)>>1;
    if(pos <= mid)
    {
        if(!L[id])
        {
            L[id] = ++cur;
            ss[L[id]] = val;
            lazy[L[id]] = pos;
        }
        else update1(L[id], l, mid, pos, val);
    }
    else
    {
        if(!R[id])
        {
            R[id] = ++cur;
            ss[R[id]] = val;
            lazy[R[id]] = pos;
        }
        else update1(R[id], mid + 1, r, pos, val);
    }
    ll s1 = 0, s2 = 0;
    if(L[id]) s1 = ss[L[id]];
    if(R[id]) s2 = ss[R[id]];
    ss[id] = gcd(s1, s2);
}
 
ll get1(int id, int l, int r, int a, int b)
{
    if(a > r || l > b) return 0;
    if(a <= l && r <= b) return ss[id];
    if(lazy[id])
    {
        if(a <= lazy[id] && lazy[id] <= b) return ss[id];
        else return 0;
    }
    int mid=(l+r)>>1;
    ll s1 = 0, s2 = 0;
    if(L[id]) s1 = get1(L[id], l, mid, a, b);
    if(R[id]) s2 = get1(R[id], mid + 1, r, a, b);
    return gcd(s1, s2);
}
 
void update2(int id, int l, int r, int i, int x, ll val)
{
    if(l == r)
    {
        if(!root[id]) root[id] = ++cur;
        update1(root[id], 1, n, x, val);
    }
    else
    {
        int mid = (l + r) >> 1;
        if(i <= mid)
        {
            if(!L[id]) L[id] = ++cur;
            update2(L[id], l, mid, i, x, val);
        }
        else
        {
            if(!R[id]) R[id] = ++cur;
            update2(R[id], mid + 1, r, i, x, val);
        }
        ll s1 = 0, s2 = 0;
        if(L[id]) s1 = get1(root[L[id]], 1, n, x, x);
        if(R[id]) s2 = get1(root[R[id]], 1, n, x, x);
        ll s3 = gcd(s1, s2);
        if(!root[id]) root[id] = ++cur;
        update1(root[id], 1, n, x, s3);
    }
}
ll get2(int id, int l, int r, int a, int b, int u, int v)
{
    if(a > r || l > b) return 0;
    else if(a <= l && r <= b)
    {
        if(root[id]) return get1(root[id], 1, n, u, v);
        else return 0;
    }
    int mid = (l + r) >> 1;
    ll s1 = 0, s2 = 0;
    if(L[id]) s1 = get2(L[id], l, mid, a, b, u, v);
    if(R[id]) s2 = get2(R[id], mid + 1, r, a, b, u, v);
    return gcd(s1, s2);
}
void init(int R, int C)
{
    m=R;
    n=C;
}
void update(int P, int Q, ll K)
{
    update2(1, 1, m, P+1, Q+1, K);
}
 
ll calculate(int P, int Q, int U, int V)
{
    return get2(1, 1, m, P+1, U+1, Q+1, V+1);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2904 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 1 ms 2392 KB Output is correct
12 Correct 1 ms 2392 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 382 ms 14160 KB Output is correct
5 Correct 257 ms 15440 KB Output is correct
6 Correct 308 ms 13232 KB Output is correct
7 Correct 334 ms 12628 KB Output is correct
8 Correct 228 ms 12832 KB Output is correct
9 Correct 325 ms 12772 KB Output is correct
10 Correct 289 ms 12368 KB Output is correct
11 Correct 1 ms 2648 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2396 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 1 ms 2392 KB Output is correct
12 Correct 612 ms 14672 KB Output is correct
13 Correct 1041 ms 12248 KB Output is correct
14 Correct 209 ms 7712 KB Output is correct
15 Correct 1237 ms 10736 KB Output is correct
16 Correct 137 ms 12112 KB Output is correct
17 Correct 490 ms 14040 KB Output is correct
18 Correct 733 ms 14016 KB Output is correct
19 Correct 647 ms 13648 KB Output is correct
20 Correct 588 ms 13136 KB Output is correct
21 Correct 1 ms 2392 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 1 ms 2392 KB Output is correct
12 Correct 374 ms 13776 KB Output is correct
13 Correct 254 ms 14748 KB Output is correct
14 Correct 302 ms 12916 KB Output is correct
15 Correct 329 ms 12576 KB Output is correct
16 Correct 230 ms 12624 KB Output is correct
17 Correct 323 ms 12732 KB Output is correct
18 Correct 284 ms 12140 KB Output is correct
19 Correct 607 ms 14856 KB Output is correct
20 Correct 1064 ms 12248 KB Output is correct
21 Correct 209 ms 6736 KB Output is correct
22 Correct 1239 ms 11904 KB Output is correct
23 Correct 146 ms 12112 KB Output is correct
24 Correct 500 ms 13864 KB Output is correct
25 Correct 742 ms 13612 KB Output is correct
26 Correct 659 ms 13576 KB Output is correct
27 Correct 589 ms 13060 KB Output is correct
28 Correct 362 ms 35668 KB Output is correct
29 Correct 908 ms 36324 KB Output is correct
30 Correct 2611 ms 32916 KB Output is correct
31 Correct 2495 ms 27832 KB Output is correct
32 Correct 433 ms 14424 KB Output is correct
33 Correct 538 ms 16160 KB Output is correct
34 Correct 179 ms 30384 KB Output is correct
35 Correct 620 ms 22084 KB Output is correct
36 Correct 1117 ms 35304 KB Output is correct
37 Correct 875 ms 34684 KB Output is correct
38 Correct 865 ms 33360 KB Output is correct
39 Correct 730 ms 29856 KB Output is correct
40 Correct 1 ms 2392 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2648 KB Output is correct
4 Correct 1 ms 2392 KB Output is correct
5 Correct 0 ms 600 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 1 ms 2392 KB Output is correct
8 Correct 1 ms 2392 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Correct 1 ms 2392 KB Output is correct
11 Correct 1 ms 2392 KB Output is correct
12 Correct 380 ms 13892 KB Output is correct
13 Correct 253 ms 15308 KB Output is correct
14 Correct 304 ms 12880 KB Output is correct
15 Correct 342 ms 12680 KB Output is correct
16 Correct 236 ms 12624 KB Output is correct
17 Correct 327 ms 12624 KB Output is correct
18 Correct 288 ms 12368 KB Output is correct
19 Correct 619 ms 14460 KB Output is correct
20 Correct 1054 ms 12576 KB Output is correct
21 Correct 208 ms 7760 KB Output is correct
22 Correct 1275 ms 11708 KB Output is correct
23 Correct 139 ms 12108 KB Output is correct
24 Correct 480 ms 13696 KB Output is correct
25 Correct 777 ms 13504 KB Output is correct
26 Correct 659 ms 14064 KB Output is correct
27 Correct 592 ms 13280 KB Output is correct
28 Correct 353 ms 35920 KB Output is correct
29 Correct 852 ms 36512 KB Output is correct
30 Correct 2570 ms 33060 KB Output is correct
31 Correct 2427 ms 28336 KB Output is correct
32 Correct 393 ms 14420 KB Output is correct
33 Correct 519 ms 16972 KB Output is correct
34 Correct 168 ms 30288 KB Output is correct
35 Correct 586 ms 22120 KB Output is correct
36 Correct 1027 ms 35152 KB Output is correct
37 Correct 884 ms 34780 KB Output is correct
38 Correct 813 ms 33156 KB Output is correct
39 Correct 517 ms 66640 KB Output is correct
40 Correct 1389 ms 60332 KB Output is correct
41 Correct 3342 ms 58328 KB Output is correct
42 Correct 3080 ms 47988 KB Output is correct
43 Correct 307 ms 54864 KB Output is correct
44 Correct 545 ms 14672 KB Output is correct
45 Correct 734 ms 29908 KB Output is correct
46 Correct 1617 ms 58828 KB Output is correct
47 Correct 1578 ms 59848 KB Output is correct
48 Correct 1453 ms 60496 KB Output is correct
49 Correct 1 ms 2392 KB Output is correct