oj.uz

Submission #19051

# Submission time Handle Problem Language Result Execution time Memory
19051 2016-02-17T10:55:35 Z tlwpdus Game (IOI13_game) C++
0 / 100
 1 ms 1284 KB 
#include "game.h"
#include<algorithm>
#include<stdio.h>

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;
}

typedef long long ll;

int R, C;

struct node {
    node *l, *r;
    ll val;
    node() {
        l=r=NULL;
        val = 0;
    }
    void update(int idx, ll num, int s=0, int e=R-1) {
        if (s==e) {
            val = num;
            return;
        }
        int m = (s+e)>>1;
        if (m<idx) {
            if (!r) r=new node();
            r->update(idx,num,m+1,e);
        }
        else {
            if (!l) l=new node();
            l->update(idx,num,s,m);
        }
        val = gcd2((l)?l->val:0,(r)?r->val:0);
    }
    ll query(int S, int E, int s=0, int e=R-1) {
        if (s>E||S>e) return 0;
        if (S<=s&&e<=E) {
            return val;
        }
        int m = (s+e)>>1;
        return gcd2((l)?l->query(S,E,s,m):0,(r)?r->query(S,E,m+1,e):0);
    }
};

void hap(node *a, node *b, node *c, int idx, int s, int e) { // a+b->c
    if (s==e) {
        c->val = gcd2(a->val,b->val);
        return;
    }
    int m = (s+e)>>1;
    if (m<idx) {
        if (!a->r) a->r=new node();
        if (!b->r) b->r=new node();
        if (!c->r) c->r=new node();
        hap(a->r,b->r,c->r,idx,m+1,e);
    }
    else {
        if (!a->l) a->l=new node();
        if (!b->l) b->l=new node();
        if (!c->l) c->l=new node();
        hap(a->l,b->l,c->l,idx,m+1,e);
    }
    c->val = gcd2(a->val,b->val);
}

struct segnode {
    segnode *l, *r;
    node *root;
    segnode() {
        l=r=NULL;
        root=new node();
    }
    void update(int idx, int idy, ll num, int s=0, int e=C-1) {
        if (s==e) {
            root->update(idx,num);
            return;
        }
        int m = (s+e)>>1;
        if (!r) r=new segnode();
        if (!l) l=new segnode();
        if (m<idy) {
            r->update(idx,idy,num,m+1,e);
        }
        else {
            l->update(idx,idy,num,s,m);
        }
        hap(l->root,r->root,root,idx,0,R-1);
    }
    ll query(int p, int q, int u, int v, int s=0, int e=C-1) {
        if (s>v||q>e) return 0;
        if (q<=s&&e<=v) {
            return root->query(p,u);
        }
        int m = (s+e)>>1;
        return gcd2((l)?l->query(p,q,u,v,s,m):0,(r)?r->query(p,q,u,v,m+1,e):0);
    }
} seg;

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

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

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

Subtask #1
0.0 / 10.0

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

Subtask #2
0.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1284 KB Output is correct
2 Correct 0 ms 1284 KB Output is correct
3 Incorrect 0 ms 1284 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0.0 / 26.0

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

Subtask #4
0.0 / 17.0

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

Subtask #5
0.0 / 20.0

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