Submission #349638

#	Time	Username	Problem	Language	Result	Execution time	Memory
349638		talant117408	Game (IOI13_game)	C++17	63 / 100	6830 ms	190428 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;
}

void pankov(){
    exit(0);
}

int n, m;
int type;

ll tree[103][400003];
ll tree2[8003][8003];

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 update_tree3(int v, int l, int r, int i, int pos, ll val){
    if(l == r){
        tree2[i][v] = val;
        return ;
    }
    int mid = (l+r) >> 1;
    if(pos <= mid) update_tree3(v<<1, l, mid, i, pos, val);
    else update_tree3((v<<1)+1, mid+1, r, i, pos, val);
    tree2[i][v] = gcd2(tree2[i][v<<1], tree2[i][(v<<1)+1]);
}

void update_tree2(int v, int l, int r, int i, int pos, ll val){
    if(l == r){
        update_tree3(1, 1, m, v, pos, val);
        return;
    }
    int mid = (l+r) >> 1;
    if(i <= mid) update_tree2(v<<1, l, mid, i, pos, val);
    else update_tree2((v<<1)+1, mid+1, r, i, pos, val);
    for(int j = 0; j < 8003; j++) tree2[v][j] = gcd2(tree2[v<<1][j], tree2[(v<<1)+1][j]);
}

ll get3(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 tree2[i][v];
    int mid = (l+r) >> 1;
    return gcd2(get3(v<<1, l, mid, i, ql, qr), get3((v<<1)+1, mid+1, r, i, ql, qr));
}

ll get2(int v, int l, int r, int ql, int qr, int y1, int y2){
    if(l > qr || ql > r) return 0;
    if(ql <= l && r <= qr) return get3(1, 1, m, v, y1, y2);
    int mid = (l+r) >> 1;
    return gcd2(get2(v<<1, l, mid, ql, qr, y1, y2), get2((v<<1)+1, mid+1, r, ql, qr, y1, y2));
}

void init(int r, int c) {
    n = r, m = c;
    if(n <= 2000 && m <= 2000) type = 2;
    else if(n <= 100 && m <= 100000) type = 1;
    else pankov();
}

void update(int P, int Q, ll K) {
    P++, Q++;
    if(type == 1)
        update_tree(1, 1, m, P, Q, K);
    else
        update_tree2(1, 1, n, P, Q, K);
}

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

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