oj.uz

Submission #12942

# Submission time Handle Problem Language Result Execution time Memory
12942 2015-01-21T06:31:10 Z gs14004 Game (IOI13_game) C++
0 / 100
 0 ms 1208 KB 
#include "game.h"
#include <cstdlib>

int r,c;
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 nodey{
    nodey() : ls(NULL), rs(NULL), v(0ll){}
    nodey *ls,*rs;
    long long v;
};
struct nodex{
    nodex() : ls(NULL), rs(NULL), ys(){}
    nodex *ls,*rs;
    nodey *ys;
}*root;

void Yadd(int y, int ps, int pe, nodey* p, long long v){
    p->v = gcd2(p->v,v);
    if(ps == pe) return;
    int pm = (ps+pe)/2;
    if(y <= pm){
        if(!p->ls) p->ls = new nodey();
        Yadd(y,ps,pm,p->ls,v);
    }
    else{
        if(!p->rs) p->rs = new nodey();
        Yadd(y,pm+1,pe,p->rs,v);
    }
}

long long Yquery(int s, int e, int ps, int pe, nodey* p){
    if(pe < s || e < ps) return 0;
    if(s <= ps && pe <= e){
        return p->v;
    }
    long long r = 0;
    int pm = (ps+pe)/2;
    if(p->ls) r = gcd2(r,Yquery(s,e,ps,pm,p->ls));
    if(p->rs) r = gcd2(r,Yquery(s,e,pm+1,pe,p->ls));
    return r;
}

void Xadd(int x, int y, int ps, int pe, nodex *p, long long v){
    if(ps == pe){
        if(!p->ys) p->ys = new nodey();
        Yadd(y,0,c-1,p->ys,v);
        return;
    }
    int pm = (ps+pe)/2;
    if(x <= pm){
        if(!p->ls) p->ls = new nodex();
        Xadd(x,y,ps,pm,p->ls,v);
        if(!p->ys) p->ys = new nodey();
        Yadd(y,0,c-1,p->ys,v);
    }
    else{
        if(!p->rs) p->rs = new nodex();
        Xadd(x,y,pm+1,pe,p->rs,v);
        if(!p->ys) p->ys = new nodey();
        Yadd(y,0,c-1,p->ys,v);
    }
}

long long Xquery(int s, int e, int ps, int pe, int sy, int ey, nodex *p){
    if(e < ps || pe < s) return 0;
    if(s <= ps && pe <= e){
        if(!p->ys) return 0;
        return Yquery(sy,ey,0,c-1,p->ys);
    }
    int pm = (ps+pe)/2;
    long long r = 0;
    if(p->ls) r = gcd2(Xquery(s,e,ps,pm,sy,ey,p->ls),r);
    if(p->rs) r = gcd2(Xquery(s,e,pm+1,pe,sy,ey,p->rs),r);
    return r;
}

void init(int R, int C) {
    root = new nodex();
    r = R, c = C;
}

void update(int P, int Q, long long K) {
    Xadd(P,Q,0,r-1,root,K);
}

long long calculate(int P, int Q, int U, int V) {
    return Xquery(P,U,0,r-1,Q,V,root);
}

Subtask #1
0.0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 1208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 1208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 1208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 17.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 1208 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 1208 KB Output isn't correct
2 Halted 0 ms 0 KB -