제출 #1001324

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1001324		rahidilbayramli	게임 (IOI13_game)	C++17	0 / 100	1 ms	348 KiB

game

#include "game.h"
#include<bits/stdc++.h>
#pragma GCC optimize("-O3")
#define ll int
#define ld long double
#define vl vector<ll>
#define vi vector<int>
#define pii pair<int, int>
#define pll pair<ll, ll>
#define all(v) v.begin(), v.end()
#define rall(v) v.rbegin(), v.rend()
#define f first
#define s second
#define pb push_back
#define p_b pop_back
using namespace std;
const ll sz = 1e4+5, sz2 = 7e6+5;
ll segtree[sz][sz], L[sz2], R[sz2], L2[sz2], R2[sz2], n, m, nxt = 1, nxt2 = 1;
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 updatey(ll vx, ll lx, ll rx, ll vy, ll ly, ll ry, ll x, ll y, ll val)
{
    if(ly == ry)
    {
        if(lx == rx)
            segtree[vx][vy] = val;
        else{
            if(!L[vx])
                L[vx] = ++nxt;
            if(!R[vx])
                R[vx] = ++nxt;
            segtree[vx][vy] = gcd2(segtree[L[vx]][vy], segtree[R[vx]][vy]);
        }
    }
    else
    {
        ll mid = (ly + ry) / 2;
        if(y <= mid){
            if(!L2[vy])
                L2[vy] = ++nxt2;
            updatey(vx, lx, rx, L2[vy], ly, mid, x, y, val);
        }
        else{
            if(!R2[vy])
                R2[vy] = ++nxt2;
            updatey(vx, lx, rx, R2[vy], mid+1, ry, x, y, val);
        }
        segtree[vx][vy] = gcd2(segtree[vx][L2[vy]], segtree[vx][R2[vy]]);
    }
}
void updatex(ll vx, ll lx, ll rx, ll x, ll y, ll val)
{
    if(lx != rx)
    {
        if(!L[vx])
            L[vx] = ++nxt;
        if(!R[vx])
            R[vx] = ++nxt;
        ll mid = (lx + rx) / 2;
        if(x <= mid)
            updatex(L[vx], lx, mid, x, y, val);
        else
            updatex(R[vx], mid+1, rx, x, y, val);
    }
    updatey(vx, lx, rx, 1, 1, m, x, y, val);
}
ll sumy(ll vx, ll vy, ll ly, ll ry, ll tly, ll tryy)
{
    if(tly > tryy)
        return 0;
    if(ly == tly && ry == tryy)
        return segtree[vx][vy];
    ll mid = (ly + ry) / 2;
    ll lans = 0, rans = 0;
    if(L2[vy])
        lans = sumy(vx, L2[vy], ly, mid, tly, min(mid, tryy));
    if(R2[vy])
        rans = sumy(vx, R2[vy], mid+1, ry, max(mid+1, tly), tryy);
    return gcd2(lans, rans);
}
ll sumx(ll vx, ll lx, ll rx, ll tlx, ll trx, ll tly, ll tryy)
{
    if(tlx > trx)
        return 0;
    if(lx == tlx && rx == trx)
        return sumy(vx, 1, 1, m, tly, tryy);
    ll mid = (lx + rx) / 2;
    ll lans = 0, rans = 0;
    if(L[vx])
        lans = sumx(L[vx], lx, mid, tlx, min(mid, trx), tly, tryy);
    if(R[vx])
        rans = sumx(R[vx], mid+1, rx, max(mid+1, tlx), trx, tly, tryy);
    return gcd2(lans, rans);
}
void init(int R, int C) {
    n = R;
    m = C;
}

void update(int P, int Q, long long K) {
    P++;
    Q++;
    updatex(1, 1, n, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    P++, Q++, U++, V++;
    return sumx(1, 1, n, P, Q, U, V);
}

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