Submission #290006

#	Time	Username	Problem	Language	Result	Execution time	Memory
290006		egekabas	Game (IOI13_game)	C++14	37 / 100	13054 ms	10152 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;
    }
    struct node{
        ll tl, tr, val;
        node *l = nullptr, *r = nullptr;
        node(ll tlval, ll trval){
            tl = tlval;
            tr = trval;
            val = 0;
        }
        node(){}
        void upd(ll idx, ll nv){
            if(tl == idx && tr == idx){
                val = nv;
                return;
            }
            ll tm = (tl+tr)/2;
            if(idx <= tm){
                if(!l)
                    l = new node(tl, tm);
                l->upd(idx, nv);
            }
            else{
                if(!r)
                    r = new node(tm+1, tr);
                r->upd(idx, nv);
            }
            ll xval = 0, yval = 0;
            if(l)
                xval =  l->val;
            if(r)
                yval = r->val;
            val = gcd2(xval, yval);        
        }
        ll get(ll lef, ll rig){
            
            if(tr < lef || rig < tl)
                return 0;
            if(lef <= tl && tr <= rig){
                return val;
            }
            ll xval = 0, yval = 0;
            if(l)
                xval = l->get(lef, rig);
            if(r)
                yval = r->get(lef, rig);
            return gcd2(xval, yval);
        }
    };
    ll r, c;
    struct seg{
        ll tl, tr;
        node *val;
        seg *l = nullptr, *r = nullptr;
        seg(ll tval, ll rval){
            tl = tval;
            tr = rval;
            val = new node(0, c-1);
        }
        seg(){}
        void upd(ll xidx, ll yidx, ll nv){
            val->upd(yidx, nv);
            if(tl == xidx && tr == xidx){
                return;
            }
            ll tm = (tl+tr)/2;
            if(xidx <= tm){
                if(!l)
                    l = new seg(tl, tm);
                l->upd(xidx, yidx, nv);
            }
            else{
                if(!r)
                    r = new seg(tm+1, tr);
                r->upd(xidx, yidx, nv);
            }
        }
        ll get(ll xl, ll xr, ll yl, ll yr){
            if(tr < xl || xr < tl)
                return 0;
            if(xl <= tl && tr <= xr){
                return val->get(yl, yr);
            }
            ll xval = 0, yval = 0;
            if(l)
                xval = l->get(xl, xr, yl, yr);
            if(r)
                yval = r->get(xl, xr, yl, yr);
            return gcd2(xval, yval);
        }
    };
    seg root;
    node ar[2009];
    void init(int R, int C) {
        r = R;
        c = C;
        for(int i = 0; i < r; ++i)
            ar[i] = node(0, c-1);
        //root = seg(0, r-1);
    }
     
    void update(int P, int Q, long long K) {
        ar[P].upd(Q, K);
        //root.upd(P, Q, K);
    }
     
    long long calculate(int P, int Q, int U, int V){    
        ll ans = 0;
        for(int i = P; i <= U; ++i)
            ans = gcd2(ans, ar[i].get(Q, V));
        return ans;
        return root.get(P, U, Q, V);
    }

Compilation message (stderr)

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   18 |  int res;
      |      ^~~

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