oj.uz

Submission #399569

# Submission time Handle Problem Language Result Execution time Memory
399569 2021-05-06T06:19:44 Z achibasadzishvili Game (IOI13_game) C++17
80 / 100
 4776 ms 256004 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 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;
        }
        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++;
        }
        if(L == R){
            return X[root].x = cur;
        }
        int mid = (L + R) / 2;
        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 , C);
}
void update(int x,int y,ll z){
    T -> set(x , y , z);
}
ll calculate(int a,int b,int c,int d){
    return T -> get(a , c , b, d);
}
/*
int main(){
    ios::sync_with_stdio(false);
    ll n,m,q;
    cin >> n >> m >> q;
    init(n , m);
    while(q--){
        ll typ;
        cin >> typ;
        if(typ == 1){
            ll x,y,z;
            cin >> x >> y >> z;
            update(x , y , z);
        }
        else {
            int a,b,c,d;
            cin >> a >> b >> c >> d;
            cout << calculate(a , b , c, d) << '\n';
        }
    } 
    
    
    
    return 0;
}
*/

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 204 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 503 ms 8608 KB Output is correct
5 Correct 379 ms 8900 KB Output is correct
6 Correct 479 ms 5784 KB Output is correct
7 Correct 514 ms 5524 KB Output is correct
8 Correct 354 ms 4420 KB Output is correct
9 Correct 492 ms 5648 KB Output is correct
10 Correct 450 ms 5228 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 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 887 ms 10208 KB Output is correct
13 Correct 1449 ms 3652 KB Output is correct
14 Correct 307 ms 848 KB Output is correct
15 Correct 1724 ms 5044 KB Output is correct
16 Correct 650 ms 9784 KB Output is correct
17 Correct 803 ms 6648 KB Output is correct
18 Correct 1246 ms 10080 KB Output is correct
19 Correct 1049 ms 10148 KB Output is correct
20 Correct 970 ms 9540 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 208 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 511 ms 8692 KB Output is correct
13 Correct 377 ms 9080 KB Output is correct
14 Correct 469 ms 5728 KB Output is correct
15 Correct 498 ms 5444 KB Output is correct
16 Correct 359 ms 4332 KB Output is correct
17 Correct 487 ms 5692 KB Output is correct
18 Correct 435 ms 5180 KB Output is correct
19 Correct 882 ms 10104 KB Output is correct
20 Correct 1471 ms 3604 KB Output is correct
21 Correct 303 ms 916 KB Output is correct
22 Correct 1697 ms 5012 KB Output is correct
23 Correct 645 ms 9788 KB Output is correct
24 Correct 758 ms 6744 KB Output is correct
25 Correct 1206 ms 10164 KB Output is correct
26 Correct 1053 ms 10184 KB Output is correct
27 Correct 1000 ms 9684 KB Output is correct
28 Correct 783 ms 142252 KB Output is correct
29 Correct 1769 ms 157088 KB Output is correct
30 Correct 4716 ms 112220 KB Output is correct
31 Correct 4519 ms 87492 KB Output is correct
32 Correct 635 ms 10356 KB Output is correct
33 Correct 817 ms 11460 KB Output is correct
34 Correct 1055 ms 150808 KB Output is correct
35 Correct 1265 ms 83484 KB Output is correct
36 Correct 2322 ms 154884 KB Output is correct
37 Correct 1991 ms 155000 KB Output is correct
38 Correct 1921 ms 154548 KB Output is correct
39 Correct 1621 ms 121572 KB Output is correct
40 Correct 1 ms 304 KB Output is correct

Subtask #5
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 2 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 517 ms 8872 KB Output is correct
13 Correct 380 ms 9116 KB Output is correct
14 Correct 460 ms 5728 KB Output is correct
15 Correct 502 ms 5624 KB Output is correct
16 Correct 360 ms 4356 KB Output is correct
17 Correct 483 ms 5572 KB Output is correct
18 Correct 448 ms 5188 KB Output is correct
19 Correct 886 ms 10180 KB Output is correct
20 Correct 1449 ms 3784 KB Output is correct
21 Correct 308 ms 896 KB Output is correct
22 Correct 1702 ms 5044 KB Output is correct
23 Correct 640 ms 9796 KB Output is correct
24 Correct 755 ms 6724 KB Output is correct
25 Correct 1204 ms 10052 KB Output is correct
26 Correct 1055 ms 10200 KB Output is correct
27 Correct 976 ms 9632 KB Output is correct
28 Correct 786 ms 142312 KB Output is correct
29 Correct 1803 ms 157080 KB Output is correct
30 Correct 4776 ms 112372 KB Output is correct
31 Correct 4486 ms 87608 KB Output is correct
32 Correct 642 ms 10180 KB Output is correct
33 Correct 797 ms 11608 KB Output is correct
34 Correct 1051 ms 150728 KB Output is correct
35 Correct 1271 ms 83532 KB Output is correct
36 Correct 2316 ms 155072 KB Output is correct
37 Correct 1961 ms 155304 KB Output is correct
38 Correct 1870 ms 154564 KB Output is correct
39 Runtime error 1093 ms 256004 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -