oj.uz

Submission #799261

# Submission time Handle Problem Language Result Execution time Memory
799261 2023-07-31T11:26:48 Z alittlemiddle Game (IOI13_game) C++14
100 / 100
 3737 ms 56396 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 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 312 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 0 ms 304 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 388 ms 10004 KB Output is correct
5 Correct 261 ms 10160 KB Output is correct
6 Correct 315 ms 7032 KB Output is correct
7 Correct 335 ms 6644 KB Output is correct
8 Correct 245 ms 6548 KB Output is correct
9 Correct 324 ms 6788 KB Output is correct
10 Correct 318 ms 6428 KB Output is correct
11 Correct 1 ms 340 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 308 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 1 ms 304 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 617 ms 11820 KB Output is correct
13 Correct 1093 ms 7388 KB Output is correct
14 Correct 218 ms 4540 KB Output is correct
15 Correct 1336 ms 8336 KB Output is correct
16 Correct 145 ms 9804 KB Output is correct
17 Correct 525 ms 7932 KB Output is correct
18 Correct 798 ms 10084 KB Output is correct
19 Correct 703 ms 10160 KB Output is correct
20 Correct 644 ms 9704 KB Output is correct
21 Correct 1 ms 340 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 308 KB Output is correct
11 Correct 1 ms 312 KB Output is correct
12 Correct 405 ms 9864 KB Output is correct
13 Correct 254 ms 10244 KB Output is correct
14 Correct 304 ms 6916 KB Output is correct
15 Correct 333 ms 6684 KB Output is correct
16 Correct 248 ms 6540 KB Output is correct
17 Correct 337 ms 6812 KB Output is correct
18 Correct 289 ms 6420 KB Output is correct
19 Correct 639 ms 11780 KB Output is correct
20 Correct 1098 ms 7280 KB Output is correct
21 Correct 234 ms 4560 KB Output is correct
22 Correct 1259 ms 8308 KB Output is correct
23 Correct 136 ms 9812 KB Output is correct
24 Correct 499 ms 7940 KB Output is correct
25 Correct 765 ms 10068 KB Output is correct
26 Correct 703 ms 10188 KB Output is correct
27 Correct 613 ms 9656 KB Output is correct
28 Correct 377 ms 28124 KB Output is correct
29 Correct 963 ms 27564 KB Output is correct
30 Correct 2654 ms 25212 KB Output is correct
31 Correct 2495 ms 21752 KB Output is correct
32 Correct 389 ms 4712 KB Output is correct
33 Correct 531 ms 6648 KB Output is correct
34 Correct 196 ms 24528 KB Output is correct
35 Correct 616 ms 15036 KB Output is correct
36 Correct 1116 ms 24820 KB Output is correct
37 Correct 911 ms 24952 KB Output is correct
38 Correct 816 ms 24388 KB Output is correct
39 Correct 765 ms 20308 KB Output is correct
40 Correct 1 ms 340 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 312 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 0 ms 340 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 1 ms 340 KB Output is correct
9 Correct 1 ms 308 KB Output is correct
10 Correct 1 ms 312 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 373 ms 9920 KB Output is correct
13 Correct 264 ms 10368 KB Output is correct
14 Correct 311 ms 6988 KB Output is correct
15 Correct 347 ms 6724 KB Output is correct
16 Correct 264 ms 6508 KB Output is correct
17 Correct 338 ms 6780 KB Output is correct
18 Correct 286 ms 6416 KB Output is correct
19 Correct 631 ms 11816 KB Output is correct
20 Correct 1069 ms 7332 KB Output is correct
21 Correct 210 ms 4552 KB Output is correct
22 Correct 1263 ms 8288 KB Output is correct
23 Correct 136 ms 9784 KB Output is correct
24 Correct 490 ms 7960 KB Output is correct
25 Correct 755 ms 10144 KB Output is correct
26 Correct 672 ms 10256 KB Output is correct
27 Correct 612 ms 9640 KB Output is correct
28 Correct 455 ms 27844 KB Output is correct
29 Correct 911 ms 27100 KB Output is correct
30 Correct 2705 ms 24984 KB Output is correct
31 Correct 2514 ms 21580 KB Output is correct
32 Correct 408 ms 4488 KB Output is correct
33 Correct 528 ms 6348 KB Output is correct
34 Correct 171 ms 24100 KB Output is correct
35 Correct 609 ms 14612 KB Output is correct
36 Correct 1089 ms 24536 KB Output is correct
37 Correct 890 ms 24416 KB Output is correct
38 Correct 840 ms 24012 KB Output is correct
39 Correct 517 ms 56396 KB Output is correct
40 Correct 1533 ms 49536 KB Output is correct
41 Correct 3737 ms 49160 KB Output is correct
42 Correct 3424 ms 41444 KB Output is correct
43 Correct 402 ms 47948 KB Output is correct
44 Correct 620 ms 4540 KB Output is correct
45 Correct 1038 ms 20140 KB Output is correct
46 Correct 1793 ms 48028 KB Output is correct
47 Correct 1805 ms 47840 KB Output is correct
48 Correct 1867 ms 47396 KB Output is correct
49 Correct 0 ms 340 KB Output is correct