Submission #250332

#	Time	Username	Problem	Language	Result	Execution time	Memory
250332		MarcoMeijer	Game (IOI13_game)	C++14	63 / 100	1617 ms	256004 KiB

game

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

//macros
typedef long long ll;
typedef pair<int, int> ii;
typedef pair<ll, ll> lll;
typedef tuple<int, int, int> iii;
typedef vector<int> vi;
typedef vector<ii> vii;
typedef vector<iii> viii;
typedef vector<ll> vll;
typedef vector<lll> vlll;
#define REP(a,b,c) for(int a=int(b); a<int(c); a++)
#define RE(a,c) REP(a,0,c)
#define RE1(a,c) REP(a,1,c+1)
#define REI(a,b,c) REP(a,b,c+1)
#define REV(a,b,c) for(int a=int(c-1); a>=int(b); a--)
#define INF 1e9
#define pb push_back
#define fi first
#define se second
#define sz size()

int R, C;

ll gcd(ll X, ll Y) {
    ll tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

struct Seg {
    int bg, ed;
    ll val;
    Seg* ls=nullptr;
    Seg* rs=nullptr;

    Seg(int l, int r, ll v=0) {
        bg=l; ed=r; val=v;
    }
    ll f(Seg* s) {
        if(s == nullptr) return 0;
        return s->val;
    }
    ll f(Seg* s, int i, int j, int l, int r) {
        if(s == nullptr) return 0;
        return s->get(i,j,l,r);
    }
    void set(int i, ll v, int l, int r) {
        int m=(l+r)/2;
        if(l == r) {
            val = v;
            return;
        }
        if(i <= m) {
            if(ls == nullptr) ls = new Seg(l,m);
            ls->set(i,v,l,m);
        } else {
            if(rs == nullptr) rs = new Seg(m+1,r);
            rs->set(i,v,m+1,r);
        }
        val = gcd(f(ls), f(rs));
    }
    ll get(int i, int j, int l, int r) {
        if(j < l || i > r) return 0;
        if(i <= l && j >= r) return val;
        int m=(l+r)/2;
        ll a = f(ls,i,j,l,m);
        ll b = f(rs,i,j,m+1,r);
        return gcd(a,b);
    }
};


struct Seg2 {
    int bg, ed;
    Seg val;
    Seg2* ls=nullptr;
    Seg2* rs=nullptr;
    
    Seg2(int l, int r) : val(0,C-1) {
        bg = l; ed = r;
    }
    ll f(Seg2* s, int j) {
        if(s == nullptr) return 0;
        return s->val.get(j,j,0,C-1);
    }
    void set(int i, int j, ll v, int l, int r) {
        int m=(l+r)/2;
        if(l == r) {
            val.set(j,v,0,C-1);
            return;
        }
        if(i <= m) {
            if(ls == nullptr) ls = new Seg2(l,m);
            ls->set(i,j,v,l,m);
        } else {
            if(rs == nullptr) rs = new Seg2(m+1,r);
            rs->set(i,j,v,m+1,r);
        }
        ll nV = 0;
        nV = gcd(f(ls,j), f(rs,j));
        val.set(j,nV,0,C-1);
    }
    ll f(Seg2* s, int i, int j, int I, int J, int l, int r) {
        if(s == nullptr) return 0;
        return s->get(i,j,I,J,l,r);
    }
    ll get(int i, int j, int I, int J, int l, int r) {
        if(j < l || i > r) return 0;
        if(i <= l && j >= r) return val.get(I,J,0,C-1);
        int m=(l+r)/2;
        ll a = f(ls,i,j,I,J,l,m);
        ll b = f(rs,i,j,I,J,m+1,r);
        return gcd(a,b);
    }
};

Seg2* SEG;

void init(int _R, int _C) {
    R = _R;
    C = _C;
    SEG = new Seg2(0,R-1);
    //RE(i,R) SEG[i] = new Seg(0,C-1);
}

void update(int P, int Q, ll K) {
    SEG->set(P,Q,K,0,R-1);
    //SEG[P]->set(Q,K,0,C-1);
}

ll calculate(int P, int Q, int U, int V) {
    /*ll ans = 0;
    REP(i,P,U+1) ans = gcd(ans, SEG[i]->get(Q,V,0,C-1));
    return ans;*/
    return SEG->get(P,U,Q,V,0,R-1);
}

Compilation message (stderr)

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

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