Submission #200107

#	Time	Username	Problem	Language	Result	Execution time	Memory
200107		johutha	Game (IOI13_game)	C++14	37 / 100	13099 ms	40184 KiB

game

#include "game.h"
#include <vector>
#include <iostream>
#include <array>
#include <cassert>

#define int long long
#define par array<int,2>

using namespace std;

int gcd(int a, int b)
{
    if (a > b) swap(a, b);
    if (a == 0) return b;
    return gcd(b % a, a);
}

struct segtree
{
    vector<int> table;

    int query(int ql, int qr, int l, int r, int pos)
    {
        if (ql <= l && r <= qr) return table[pos];
        if (r < ql || qr < l) return 0;
        return gcd(query(ql, qr, l, (l + r)/2, 2*pos + 1), query(ql, qr, (l + r)/2 + 1, r, 2*pos + 2));
    }

    void update(int k, int v, int l, int r, int pos)
    {
        if (l == r)
        {
            table[pos] = v;
            return;
        }
        if (k <= (l + r)/2) update(k, v, l, (l + r)/2, 2*pos + 1);
        else update(k, v, (l + r)/2 + 1, r, 2*pos + 2);
        table[pos] = gcd(table[2*pos + 1], table[2*pos + 2]);
    }
};

vector<segtree> sts;
int r, c;

void init(signed R, signed C)
{
    r = R;
    c = C;
    sts.resize(R);
    for (int i = 0; i < R; i++) sts[i].table.resize(4*C);
}

void update(signed P, signed Q, int K)
{
    // cout << "\n";
    sts[P].update(Q, K, 0, c - 1, 0);
}
 
int calculate(signed P, signed Q, signed U, signed V) 
{
    // cout << "\n";
    if (U < P) swap(U, P);
    if (V < Q) swap(Q, V);
    
    int ret = 0;

    for (int i = P; i <= U; i++)
    {
        ret = gcd(ret, sts[i].query(Q, V, 0, c - 1, 0));
        // cout << i << " " << sts[i].query(Q, V, 0, c - 1, 0) << "\n";
    }

    return ret;
}

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: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20