Submission #290150

#	Time	Username	Problem	Language	Result	Execution time	Memory
290150		egekabas	Game (IOI13_game)	C++14	63 / 100	2474 ms	256004 KiB

game

#include "game.h"
#include <bits/stdc++.h>
#define all(x) (x).begin(), (x).end()
#define ff first
#define ss second
#define pb push_back
#define mp make_pair
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<ull, ull> pull;
typedef pair<ll, ll> pii;
typedef pair<ld, ld> pld;
long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
int r, c, rr;
    
struct node{
    ll val = 0;
    node *l = nullptr, *r = nullptr;
    
    void upd(int idx, ll nv, int tl, int tr){
        if(tl == idx && tr == idx){
            val = nv;
            return;
        }
        int tm = (tl+tr)/2;
        if(idx <= tm){
            if(!l)
                l = new node();
            l->upd(idx, nv, tl, tm);
        }
        else{
            if(!r)
                r = new node();
            r->upd(idx, nv, tm+1, tr);
        }
        ll xval = 0, yval = 0;
        if(l)
            xval =  l->val;
        if(r)
            yval = r->val;
        val = gcd2(xval, yval);        
    }
    ll get(int lef, int rig, int tl, int tr){
        if(tr < lef || rig < tl)
            return 0;
        if(lef <= tl && tr <= rig){
            return val;
        }
        ll xval = 0, yval = 0;
        int tm = (tl+tr)/2;
        if(l)
            xval = l->get(lef, rig, tl, tm);
        if(r)
            yval = r->get(lef, rig, tm+1, tr);
        return gcd2(xval, yval);
    }
};
struct seg{
    node *val;
    seg *l = nullptr, *r = nullptr;
    seg(){
        val = new node();
    }
    void upd(int xidx, int yidx, ll nv, int tl, int tr){    
        if(xidx < tl || xidx > tr) return;
        if(tl == xidx && tr == xidx){
            val->upd(yidx, nv, 0, c-1);
            return;
        }
        int tm = (tl+tr)/2;
        if(xidx <= tm){
            if(!l)
                l = new seg();
            l->upd(xidx, yidx, nv, tl, tm);
        }
        else{
            if(!r)
                r = new seg();
            r->upd(xidx, yidx, nv, tm+1, tr);
        }
        ll xval = 0, yval = 0;
        if(l)
            xval = l->val->get(yidx, yidx, 0, c-1);
        if(r)
            yval = r->val->get(yidx, yidx, 0, c-1);
        nv = gcd2(xval, yval);
        val->upd(yidx, nv, 0, c-1);
    }
    ll get(int xl, int xr, int yl, int yr, int tl, int tr){
        if(tr < xl || xr < tl)
            return 0;
        if(xl <= tl && tr <= xr){
            return val->get(yl, yr, 0, c-1);
        }
        ll xval = 0, yval = 0;
        int tm = (tl+tr)/2;
        if(l)
            xval = l->get(xl, xr, yl, yr, tl, tm);
        if(r)
            yval = r->get(xl, xr, yl, yr, tm+1, tr);
        return gcd2(xval, yval);
    }
};
seg root;
void init(int R, int C) {
    r = rr = R;
    c = C;
    root =  seg();
}
    
void update(int P, int Q, long long K) {
    root.upd(P, Q, K, 0, r-1);
}
    
long long calculate(int P, int Q, int U, int V){    
    return root.get(P, U, Q, V, 0, r-1);
}

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20