Submission #524500

#	Time	Username	Problem	Language	Result	Execution time	Memory
524500		prvocislo	Game (IOI13_game)	C++17	0 / 100	76 ms	165624 KiB

game

#include "game.h"
#include <algorithm>
#include <iostream>
#include <string>
#include <random>
#include <chrono>
#include <vector>
#include <cmath>
#include <set>
#include <map>
#include <iomanip>
#include <queue>
#include <bitset>
#include <cmath>
#include <cassert>
typedef long long ll;
typedef long double ld;
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;
}
const int maxn = 1 << 30;
struct node
{
    int idx;
    ll val, g;
    node* l, * r;
    node() { idx = -1, val = 0, g = 0, l = NULL, r = NULL; }
} st[2 * 60 * 22005];
int cnt = 0;
struct node2d
{
    node *n;
    node2d* l, * r;
    node2d() { n = NULL, l = NULL, r = NULL; }
} st2d[2 * 60 * 22005];
int cnt2 = 0;
void update1d(int idx, ll val, int myl, int myr, node *n)
{
    if (myr < idx || myl > idx) return;
    if (n->idx == -1 || n->idx == idx) return n->val = val, n->idx = idx, void();
    if (n->l == NULL) n->l = &st[cnt++], n->r = &st[cnt++];
    update1d(idx, val, myl, (myl + myr) / 2, n->l);
    update1d(idx, val, (myl + myr) / 2 + 1, myr, n->r);
    n->g = gcd2(gcd2(n->l->val, n->l->g), gcd2(n->r->val, n->r->g));
}
ll query1d(int li, int ri, int myl, int myr, node* n)
{
    if (n == NULL || ri < myl || li > myr) return 0;
    ll ans = ((li <= n->idx && n->idx <= ri) ? n->val : 0ll);
    if (li <= myl && myr <= ri) return gcd2(ans, n->g);
    return gcd2(ans, gcd2(query1d(li, ri, myl, (myl + myr) / 2, n->l), query1d(li, ri, (myl + myr) / 2 + 1, myr, n->r)));
}
void update2d(int x, int y, ll val, int myl, int myr, node2d* n)
{
    if (myr < x || myl > x) return;
    update1d(y, val, 0, maxn - 1, n->n);
    if (myl == myr) return;
    if (n->l == NULL) n->l = new node2d(), n->l->n = &st[cnt++];
    if (n->r == NULL) n->r = new node2d(), n->r->n = &st[cnt++];
    update2d(x, y, val, myl, (myl + myr) / 2, n->l);
    update2d(x, y, val, (myl + myr) / 2 + 1, myr, n->r);
}
ll query2d(int x1, int y1, int x2, int y2, int myl, int myr, node2d* n)
{
    if (n == NULL || x2 < myl || x1 > myr) return 0;
    if (x1 <= myl && myr <= x2) return query1d(y1, y2, 0, maxn - 1, n->n);
    return gcd2(query2d(x1, y1, x2, y2, myl, (myl + myr) / 2, n->l), query2d(x1, y1, x2, y2, (myl + myr) / 2 + 1, myr, n->r));
}
void init(int R, int C) 
{
    st2d[cnt2++].n = &st[cnt++];
}
void update(int x, int y, long long k) 
{
    update2d(x, y, k, 0, maxn - 1, &st2d[0]);
}
long long calculate(int x1, int y1, int x2, int y2)
{
    return query2d(x1, y1, x2, y2, 0, maxn - 1, &st2d[0]);
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20