oj.uz

Submission #399574

# Submission time Handle Problem Language Result Execution time Memory
399574 2021-05-06T06:36:13 Z achibasadzishvili Game (IOI13_game) C++17
100 / 100
 5708 ms 93020 KB 
#include<bits/stdc++.h>
#include "game.h"
#define ll long long
#define f first
#define s second
#define pb push_back
using namespace std;

ll s1 = 1, s2 = 1;
ll gcd(ll x,ll y){
    return __gcd(x , y);
}
struct T {ll x; int p,l,r;} X[50000000];
struct seg1 {
    int N,root;
    seg1(int n) : N(n){root = 0;}
    
    ll get(int root,int L,int R,int l,int r){
        if(L > r || R < l || !root)return 0;
        if(L >= l && R <= r){
            return X[root].x;
        }
        if(X[root].p){
            if(X[root].p >= l && X[root].p <= r)return X[root].x;
            return 0;
        }
        int mid = (L + R) / 2;
        ll k1 = get(X[root].l , L , mid , l , r);
        ll k2 = get(X[root].r , mid + 1 , R , l , r);
        return gcd(k1 , k2);
    }
    ll get(int l,int r){
        return get(root , 0 , N , l , r);
    }
    ll set(int& root,int L,int R,int ind,ll cur){
        if(ind > R || ind < L)return X[root].x;
        if(!root){
            root = s1++;
            X[root].x = cur;
            X[root].p = ind;
            return cur;
        }
        if(L == R){
            return X[root].x = cur;
        }
        int mid = (L + R) / 2;
        if(X[root].p){
            set(X[root].l , L , mid , X[root].p , X[root].x);
            set(X[root].r , mid + 1 , R , X[root].p , X[root].x);
            X[root].p = 0;
        }
        ll k1 = set(X[root].l , L , mid , ind , cur);
        ll k2 = set(X[root].r , mid + 1 , R , ind , cur);
        return X[root].x = gcd(k1 , k2);
    }
    void set(int x,ll y){
        set(root , 0 , N , x , y);
    }
};
struct T2 {seg1* x; int l,r;} Y[50000000];
struct seg2 {
    int N,M,root;
    seg2(int n,int m) : N(n) , M(m) {root = 0;}
    
    ll get(int root ,int L,int R,int l,int r,int nl,int nr){
        if(L > r || R < l || !root)return 0;
        //cout << L << " " << R << '\n';
        if(L >= l && R <= r){
            //cout << L << " " << nl << " " << nr << " " << root << '\n';
            //cout << Y[root].x -> get(nl , nr) << '\n';
            return Y[root].x -> get(nl,nr);
        }
        int mid = (L + R) / 2;
        ll k1 = get(Y[root].l , L , mid , l , r , nl , nr);
        ll k2 = get(Y[root].r , mid + 1 , R , l , r , nl , nr);
        return gcd(k1 , k2);
    }
    ll get(int a,int b,int c,int d){
        return get(root , 0 , N , a , b , c , d);
    }
    
    ll set(int& root,int L,int R,int ind,int nind,ll cur){
        if(ind < L || ind > R){
            if(!root)return 0;
            else return Y[root].x -> get(nind , nind);
        }
        if(!root){
            root = s2++;
            Y[root].x = new seg1(M);
        }
        //cout << root << " " << L << " " << R << '\n';
        if(L == R){
            if(root == 5){
                //cout << nind << " - " << cur << '\n';
            }
            Y[root].x -> set(nind , cur);
            return cur;
        }
        int mid = (L + R) / 2;
        ll k1 = set(Y[root].l , L , mid , ind, nind , cur);
        ll k2 = set(Y[root].r , mid + 1 , R , ind , nind , cur);
        ll y = gcd(k1 , k2);
        Y[root].x -> set(nind , y);
        return y;
    }
    void set(int a,int b,ll c){
        set(root , 0 , N , a , b , c);
    }
} *T;
void init(int R,int C){
    T = new seg2(R + 10 , C + 10);
}
void update(int x,int y,ll z){
    x++;
    y++;
    T -> set(x , y , z);
}
ll calculate(int a,int b,int c,int d){
    a++;b++;c++;d++;
    return T -> get(a , c , b, d);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 454 ms 7324 KB Output is correct
5 Correct 381 ms 7720 KB Output is correct
6 Correct 461 ms 4420 KB Output is correct
7 Correct 484 ms 4136 KB Output is correct
8 Correct 356 ms 3336 KB Output is correct
9 Correct 472 ms 4192 KB Output is correct
10 Correct 457 ms 3832 KB Output is correct
11 Correct 1 ms 204 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 336 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 882 ms 8788 KB Output is correct
13 Correct 1508 ms 3896 KB Output is correct
14 Correct 306 ms 836 KB Output is correct
15 Correct 1847 ms 5136 KB Output is correct
16 Correct 1536 ms 6552 KB Output is correct
17 Correct 706 ms 4484 KB Output is correct
18 Correct 1104 ms 7032 KB Output is correct
19 Correct 956 ms 7000 KB Output is correct
20 Correct 858 ms 6432 KB Output is correct
21 Correct 1 ms 204 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 483 ms 7540 KB Output is correct
13 Correct 376 ms 7680 KB Output is correct
14 Correct 441 ms 4508 KB Output is correct
15 Correct 490 ms 4268 KB Output is correct
16 Correct 335 ms 3524 KB Output is correct
17 Correct 474 ms 4548 KB Output is correct
18 Correct 427 ms 3892 KB Output is correct
19 Correct 841 ms 8772 KB Output is correct
20 Correct 1513 ms 3996 KB Output is correct
21 Correct 313 ms 968 KB Output is correct
22 Correct 1818 ms 5452 KB Output is correct
23 Correct 1522 ms 6580 KB Output is correct
24 Correct 682 ms 4548 KB Output is correct
25 Correct 1027 ms 6996 KB Output is correct
26 Correct 928 ms 7108 KB Output is correct
27 Correct 860 ms 6576 KB Output is correct
28 Correct 527 ms 25156 KB Output is correct
29 Correct 1272 ms 24836 KB Output is correct
30 Correct 4569 ms 22544 KB Output is correct
31 Correct 4353 ms 42268 KB Output is correct
32 Correct 683 ms 1576 KB Output is correct
33 Correct 900 ms 3544 KB Output is correct
34 Correct 2471 ms 21852 KB Output is correct
35 Correct 869 ms 12040 KB Output is correct
36 Correct 1587 ms 21936 KB Output is correct
37 Correct 1288 ms 22196 KB Output is correct
38 Correct 1241 ms 21568 KB Output is correct
39 Correct 1083 ms 17332 KB Output is correct
40 Correct 1 ms 204 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 2 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 457 ms 7368 KB Output is correct
13 Correct 378 ms 7800 KB Output is correct
14 Correct 444 ms 4452 KB Output is correct
15 Correct 483 ms 4164 KB Output is correct
16 Correct 339 ms 3440 KB Output is correct
17 Correct 479 ms 4164 KB Output is correct
18 Correct 426 ms 3840 KB Output is correct
19 Correct 856 ms 8644 KB Output is correct
20 Correct 1521 ms 3920 KB Output is correct
21 Correct 307 ms 908 KB Output is correct
22 Correct 1824 ms 5248 KB Output is correct
23 Correct 1529 ms 6568 KB Output is correct
24 Correct 684 ms 4420 KB Output is correct
25 Correct 1046 ms 6724 KB Output is correct
26 Correct 928 ms 6844 KB Output is correct
27 Correct 882 ms 6260 KB Output is correct
28 Correct 546 ms 25184 KB Output is correct
29 Correct 1399 ms 24532 KB Output is correct
30 Correct 4615 ms 22208 KB Output is correct
31 Correct 4504 ms 42228 KB Output is correct
32 Correct 691 ms 1524 KB Output is correct
33 Correct 878 ms 3556 KB Output is correct
34 Correct 2466 ms 21568 KB Output is correct
35 Correct 898 ms 12028 KB Output is correct
36 Correct 1678 ms 21856 KB Output is correct
37 Correct 1297 ms 22132 KB Output is correct
38 Correct 1355 ms 21460 KB Output is correct
39 Correct 763 ms 64784 KB Output is correct
40 Correct 1998 ms 57712 KB Output is correct
41 Correct 5708 ms 53832 KB Output is correct
42 Correct 5617 ms 93020 KB Output is correct
43 Correct 3008 ms 52428 KB Output is correct
44 Correct 990 ms 10740 KB Output is correct
45 Correct 1196 ms 27172 KB Output is correct
46 Correct 2304 ms 56472 KB Output is correct
47 Correct 2293 ms 56508 KB Output is correct
48 Correct 2156 ms 56004 KB Output is correct
49 Correct 1 ms 204 KB Output is correct