Submission #1025553

#	Time	Username	Problem	Language	Result	Execution time	Memory
1025553		socpite	Game (IOI13_game)	C++17	63 / 100	1294 ms	256000 KiB

game

#include <bits/stdc++.h>
using namespace std;

#include "game.h"

const int maxn = 1e9;

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 st1d{
    st1d *lc, *rc;
    int l, r;
    long long val;
    st1d(int _l, int _r): val(0), l(_l), r(_r), lc(nullptr), rc(nullptr){}
    void add(int y, long long p){
        if(l == r){
            val = p;
            return;
        }
        int mid = (l+r)>>1;
        if(y <= mid){
            if(!lc)lc = new st1d(l, mid);
            lc->add(y, p);
            if(rc)val = gcd2(lc->val, rc->val);
            else val = lc->val;
        }
        else {
            if(!rc)rc = new st1d(mid+1, r);
            rc->add(y, p);
            if(lc)val = gcd2(lc->val, rc->val);
            else val = rc->val;
        }
    }
    void cpy(st1d &b, int y){
        val = b.val;
        if(l == r)return;
        int mid = (l+r)>>1;
        if(y <= mid){
            if(!lc)lc = new st1d(l, mid);
            lc->cpy(*b.lc, y);
        }
        else {
            if(!rc)rc = new st1d(mid+1, r);
            rc->cpy(*b.rc, y);
        }
    }
    void merge(st1d &bl, st1d &br, int y){
        val = gcd2(bl.val, br.val);
        if(l == r)return;
        int mid = (l+r)>>1;
        if(y <= mid){
            if(!lc)lc = new st1d(l, mid);
            if(!bl.lc)lc->cpy(*br.lc, y);
            else if(!br.lc)lc->cpy(*bl.lc, y);
            else lc->merge(*bl.lc, *br.lc, y);
            
        }
        else {
            if(!rc)rc = new st1d(mid+1, r);
            if(!bl.rc)rc->cpy(*br.rc, y);
            else if(!br.rc)rc->cpy(*bl.rc, y);
            else rc->merge(*bl.rc, *br.rc, y);
        }
    }
    long long query(int ql, int qr){
        if(ql > r || l > qr)return 0;
        if(ql <= l && r <= qr)return val;
        long long lhs = lc ? lc->query(ql, qr) : 0, rhs = rc ? rc->query(ql, qr) : 0;
        return gcd2(lhs, rhs);
    }
};

struct st2d{
    st2d *lc, *rc;
    int l, r;
    st1d st;
    st2d(int _l, int _r): st(0, maxn), l(_l), r(_r), lc(nullptr), rc(nullptr){}
    void add(int x, int y, long long p){
        if(l == r){
            st.add(y, p);
            return;
        }
        int mid = (l+r)>>1;
        if(x <= mid){
            if(!lc)lc = new st2d(l, mid);
            lc->add(x, y, p);
            if(rc)st.merge(lc->st, rc->st, y);
            else st.cpy(lc->st, y);
        }
        else {
            if(!rc)rc = new st2d(mid+1, r);
            rc->add(x, y, p);
            if(lc)st.merge(lc->st, rc->st, y);
            else st.cpy(rc->st, y);
        }
    }
    long long query(int p, int q, int u, int v){
        if(l > u || r < p)return 0;
        if(p <= l && r <= u)return st.query(q, v);
        long long lhs = lc ? lc->query(p, q, u, v) : 0, rhs = rc ? rc->query(p, q, u, v) : 0;
        return gcd2(lhs, rhs);
    }

}rt(0, maxn);

void init(int R, int C) {
    
}

void update(int P, int Q, long long K) {
    rt.add(P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    /* ... */
    return rt.query(P, Q, U, V);
}

Compilation message (stderr)

game.cpp: In constructor 'st1d::st1d(int, int)':
game.cpp:21:15: warning: 'st1d::val' will be initialized after [-Wreorder]
   21 |     long long val;
      |               ^~~
game.cpp:20:9: warning:   'int st1d::l' [-Wreorder]
   20 |     int l, r;
      |         ^
game.cpp:22:5: warning:   when initialized here [-Wreorder]
   22 |     st1d(int _l, int _r): val(0), l(_l), r(_r), lc(nullptr), rc(nullptr){}
      |     ^~~~
game.cpp:20:12: warning: 'st1d::r' will be initialized after [-Wreorder]
   20 |     int l, r;
      |            ^
game.cpp:19:11: warning:   'st1d* st1d::lc' [-Wreorder]
   19 |     st1d *lc, *rc;
      |           ^~
game.cpp:22:5: warning:   when initialized here [-Wreorder]
   22 |     st1d(int _l, int _r): val(0), l(_l), r(_r), lc(nullptr), rc(nullptr){}
      |     ^~~~
game.cpp: In constructor 'st2d::st2d(int, int)':
game.cpp:84:10: warning: 'st2d::st' will be initialized after [-Wreorder]
   84 |     st1d st;
      |          ^~
game.cpp:83:9: warning:   'int st2d::l' [-Wreorder]
   83 |     int l, r;
      |         ^
game.cpp:85:5: warning:   when initialized here [-Wreorder]
   85 |     st2d(int _l, int _r): st(0, maxn), l(_l), r(_r), lc(nullptr), rc(nullptr){}
      |     ^~~~
game.cpp:83:12: warning: 'st2d::r' will be initialized after [-Wreorder]
   83 |     int l, r;
      |            ^
game.cpp:82:11: warning:   'st2d* st2d::lc' [-Wreorder]
   82 |     st2d *lc, *rc;
      |           ^~
game.cpp:85:5: warning:   when initialized here [-Wreorder]
   85 |     st2d(int _l, int _r): st(0, maxn), l(_l), r(_r), lc(nullptr), rc(nullptr){}
      |     ^~~~

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