oj.uz

Submission #27240

# Submission time Handle Problem Language Result Execution time Memory
27240 2017-07-11T11:49:32 Z tlwpdus Game (IOI13_game) C++11
0 / 100
 0 ms 2208 KB 
#include "game.h"
#include <bits/stdc++.h>

typedef long long ll;

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

ll R, C;
int x, y; ll val;
int sx, sy, ex, ey;

struct node1 {
    ll val;
    node1 *l, *r;
    node1() {val = 0; l = r = NULL;}
    void mer() {val = gcd2(l?l->val:0,r?r->val:0);}
    void upd(int s = 0, int e = C-1) {
        if (s==e) {
            val = ::val;
            return;
        }
        int m = (s+e)>>1;
        if (y<=m) {
            if (!l) l = new node1();
            l->upd(s,m);
        }
        else {
            if (!r) r = new node1();
            r->upd(m+1,e);
        }
        mer();
    }
    void upd(node1 *a, node1 *b, int s = 0, int e = C-1) {
        if (s==e) {
            val = gcd2(a?a->val:0,b?b->val:0);
            return;
        }
        int m = (s+e)>>1;
        if (y<=m) {
            if (!l) l = new node1();
            l->upd(a?a->l:0,b?b->l:0,s,m);
        }
        else {
            if (!r) r = new node1();
            r->upd(a?a->r:0,b?b->r:0,m+1,e);
        }
        mer();
    }
    ll getv(int s = 0, int e = C-1) {
        if (e<sy||ey<s) return 0;
        if (sy<=s&&e<=ey) return val;
        int m = (s+e)>>1;
        return gcd2(l?l->getv(s,m):0,r?r->getv(m+1,e):0);
    }
};

struct node2 {
    node1 *head;
    node2 *l, *r;
    node2() {head = new node1(); l = r = NULL;}
    void mer() {
        head->upd(l?l->head:0,r?r->head:0);
    }
    void upd(int s = 0, int e = R-1) {
        head->upd();
        if (s==e) return;
        int m = (s+e)>>1;
        if (x<=m) {
            if (!l) l = new node2();
            l -> upd(s,m);
        }
        else {
            if (!r) r = new node2();
            r -> upd(m+1,e);
        }
    }
    ll getv(int s = 0, int e = R-1) {
        if (e<sx||ex<s) return 0;
        if (sx<=s&&e<=ex) return head->getv();
        int m = (s+e)>>1;
        return gcd2(l?l->getv(s,m):0,r?r->getv(m+1,e):0);
    }
} *tree;

void upd(int x, int y, ll val) {
    ::x = x; ::y = y; ::val = val;
    tree->upd();
}

ll calc(int sx, int sy, int ex, int ey) {
    ::sx=sx;::ex=ex;::sy=sy;::ey=ey;
    return tree->getv();
}

void init(int R, int C) {
    ::R = R; ::C = C;
    tree = new node2();
}

void update(int P, int Q, ll K) {
    upd(P,Q,K);
}

ll calculate(int P, int Q, int U, int V) {
    return calc(P,Q,U,V);
}

Compilation message

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
0 / 10.0

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

Subtask #2
0 / 27.0

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

Subtask #3
0 / 26.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 20.0

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