Submission #399569

#	Time	Username	Problem	Language	Result	Execution time	Memory
399569		achibasadzishvili	Game (IOI13_game)	C++17	80 / 100	4776 ms	256004 KiB

game

#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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 0 / 20