Submission #399574

#	Time	Username	Problem	Language	Result	Execution time	Memory
399574		achibasadzishvili	Game (IOI13_game)	C++17	100 / 100	5708 ms	93020 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 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 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20