oj.uz

Submission #159791

# Submission time Handle Problem Language Result Execution time Memory
159791 2019-10-24T15:37:47 Z rama_pang Game (IOI13_game) C++14
0 / 100
 3 ms 632 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
using lint = long long;

int R, C;

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

struct SegmentTreeInside {
    struct Node {
        lint val;
        Node *lc, *rc;

        Node(): val(0), lc(NULL), rc(NULL) {}
    };

    Node *root;

    SegmentTreeInside(): root(NULL) {}

    void update(Node *n, int tl, int tr, int p, lint x) {
        if (tl == tr) {
            n->val = x;
            return;
        }

        if (n->lc == NULL) n->lc = new Node();
        if (n->rc == NULL) n->rc = new Node();
        
        int mid = (tl + tr) / 2;
        if (p <= mid) 
            update(n->lc, tl, mid, p, x);
        else
            update(n->rc, mid + 1, tr, p, x);

        n->val = gcd(n->lc->val, n->rc->val);   
    }

    lint query(Node *n, int tl, int tr, int le, int ri) {
        if (tr < le || tl > ri || tl > tr) return 0;
        if (le <= tl && tr <= ri) return n->val;
        
        int mid = (tl + tr) / 2;
        if (n->lc == NULL) n->lc = new Node();
        if (n->rc == NULL) n->rc = new Node();
        
        return gcd(query(n->lc, tl, mid, le, ri), query(n->rc, mid + 1, tr, le, ri));
    }

};

struct SegmentTree {
    struct Node {
        SegmentTreeInside seg;
        Node *lc, *rc;

        Node() {
            lc = rc = NULL;
            seg.root = new SegmentTreeInside::Node();
        }
    };

    Node *root;

    SegmentTree() {
        root = new Node();
    }

    void update(Node *n, int tl, int tr, int p, int q, lint x) {
        if (tl == tr) {
            n->seg.update(n->seg.root, 0, C - 1, q, x);
            return;
        }
        int mid = (tl + tr) / 2;
        if (n->lc == NULL) n->lc = new Node();
        if (n->rc == NULL) n->rc = new Node();
        
        if (p <= mid) 
            update(n->lc, tl, mid, p, q, x);
        else
            update(n->rc, mid + 1, tr, p, q, x);

        n->seg.update(n->seg.root, 0, C - 1, q, x);
    }

    lint query(Node *n, int tl, int tr, int le, int ri, int lo, int hi) {
        if (tr < le || tl > ri || tl > tr) return 0;
        if (le <= tl && tr <= ri) return n->seg.query(n->seg.root, 0, C - 1, lo, hi);

        int mid = (tl + tr) / 2;
        if (n->lc == NULL) n->lc = new Node();
        if (n->rc == NULL) n->rc = new Node();

        return gcd(query(n->lc, tl, mid, le, ri, lo, hi), query(n->rc, mid + 1, tr, le, ri, lo, hi));
    }

};

SegmentTree solver;

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

void update(int P, int Q, lint K) {
    solver.update(solver.root, 0, R - 1, P, Q, K);
}

lint calculate(int P, int Q, int U, int V) {
    return solver.query(solver.root, 0, R - 1, P, U, Q, 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 2 ms 376 KB Output is correct
2 Incorrect 3 ms 632 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

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

Subtask #3
0 / 26.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 20.0

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