Submission #256427

#	Time	Username	Problem	Language	Result	Execution time	Memory
256427		A02	Game (IOI13_game)	C++14	63 / 100	1154 ms	256004 KiB

game

#include "game.h"
#include <vector>
#include <algorithm>
#include <set>
#include <utility>
#include <iostream>

using namespace std;

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


void update_seg_tree(vector<long long> &tree, long long p, long long t){

    long long N = tree.size() / 2;

    tree[p + N] = t;

    for (p = (p + N) / 2; 0 < p; p /= 2){

        tree[p] = gcd2(tree[2 * p], tree[2 * p + 1]);

    }

}

long long query_seg_tree(vector<long long> &tree, long long l, long long r){

    long long N = tree.size() / 2;
    long long total = 0;

    for (l += N, r += N; l < r; l /= 2, r /= 2){

        if (l % 2 == 1){
            total = gcd2(total, tree[l++]);
        }
        if (r % 2 == 1){
            total = gcd2(total, tree[--r]);
        }

    }

    return total;
}

void update_2Dseg_tree(vector<vector<long long> > &tree, long long r, long long c, long long t){

    long long N = tree.size() / 2;

    update_seg_tree(tree[r + N], c, t);

    for (r = (r + N) / 2; 0 < r; r /= 2){

        update_seg_tree(tree[r], c, gcd2(query_seg_tree(tree[2 * r], c, c + 1), query_seg_tree(tree[2 * r + 1], c, c + 1)));

    }

}

long long query_2Dseg_tree(vector<vector<long long> > &tree, long long lr, long long rr, long long lc, long long rc){

    long long N = tree.size() / 2;
    long long total = 0;

    for (lr += N, rr += N; lr < rr; lr /= 2, rr /= 2){

        if (lr % 2 == 1){
            total = gcd2(total, query_seg_tree(tree[lr++], lc, rc));
        }
        if (rr % 2 == 1){
            total = gcd2(total, query_seg_tree(tree[--rr], lc, rc));
        }

    }

    return total;
}

vector<vector<long long> > seg_tree;

void init(int R, int C) {

    seg_tree = vector<vector<long long> > (2 * R, vector<long long> (2 * C, 0));

}

void update(int P, int Q, long long K) {
    //cout << "update: " << P << ' ' << Q << ' ' << K << endl;
    update_2Dseg_tree(seg_tree, P, Q, K);
    //cout << ' ' << query_2Dseg_tree(seg_tree, 0, 1, 0, 3) << endl;
}

long long calculate(int P, int Q, int U, int V) {
    //cout << "calculate: " << P << ' ' << Q << ' '<< U << ' ' << V << endl;
    return query_2Dseg_tree(seg_tree, P, U + 1, Q, V + 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