Submission #349629

#	Time	Username	Problem	Language	Result	Execution time	Memory
349629		talant117408	Game (IOI13_game)	C++17	37 / 100	1125 ms	26060 KiB

game

#include <bits/stdc++.h>
#include "game.h"
#ifndef EVAL
#include "grader.cpp"
#endif

using namespace std;

typedef long long ll;
typedef pair <int, int> pii;
typedef pair <ll, ll> pll;

#define precision(n) fixed << setprecision(n)
#define pb push_back
#define ub upper_bound
#define lb lower_bound
#define mp make_pair
#define eps (double)1e-9
#define PI 2*acos(0.0)
#define endl "\n"
#define sz(v) int((v).size())
#define all(v) v.begin(),v.end()
#define rall(v) v.rbegin(),v.rend()
#define do_not_disturb ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
#define OK cout << "OK" << endl;


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

int n, m;

ll tree[103][400003];

void update_tree(int v, int l, int r, int i, int pos, ll val){
    if(l == r){
        tree[i][v] = val;
        return;
    }
    int mid = (l+r) >> 1;
    if(pos <= mid) update_tree(v<<1, l, mid, i, pos, val);
    else update_tree((v<<1)+1, mid+1, r, i, pos, val);
    tree[i][v] = gcd2(tree[i][v<<1], tree[i][(v<<1)+1]);
}

ll get(int v, int l, int r, int i, int ql, int qr){
    if(l > qr || ql > r) return 0;
    if(ql <= l && r <= qr) return tree[i][v];
    int mid = (l+r) >> 1;
    return gcd2(get(v<<1, l, mid, i, ql, qr), get((v<<1)+1, mid+1, r, i, ql, qr));
}

void init(int r, int c) {
    n = r, m = c;
    if(n > 100) exit(0);
}

void update(int P, int Q, ll K) {
    P++, Q++;
    update_tree(1, 1, m, P, Q, K);
}

ll calculate(int x1, int y1, int x2, int y2) {
    ll ans = 0;
    x1++, y1++, x2++, y2++;
    for(int i = x1; i <= x2; i++){
        ans = gcd2(ans, get(1, 1, m, i, y1, y2));
    }
    return ans;
}

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