Submission #675455

#	Time	Username	Problem	Language	Result	Execution time	Memory
675455		tae826	Game (IOI13_game)	C++17	0 / 100	86 ms	196172 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int gapcnt, R, C;
#pragma pack(4)
struct YNode {
    ll gap;
    int lf = -1, rg = -1, lazy = -1;
} gap[10010010], trash;

inline ll _gcd(ll x, ll y) { if(x == 0 || y == 0) return x+y; return __gcd(x, y); }

ll queryY(int now, int s, int e, int si, int ei) {
    if(s > ei || e < si) return 0;
    if(gap[now].lazy > 0) {
        if(gap[now].lazy >= si && gap[now].lazy <= ei) return gap[now].gap;
        else return 0;
    }
    if(s >= si && e <= ei) return gap[now].gap;
    ll lv = 0, rv = 0, ret = 0, m = s+e>>1;
    if(gap[now].lf != -1) lv = queryY(gap[now].lf, s, m, si, ei);
    if(gap[now].rg != -1) rv = queryY(gap[now].rg, m+1, e, si, ei);
    return _gcd(ret, _gcd(lv, rv));
}

ll queryX(int n, int s, int e, int si, int ei, int ssi, int eei) {
    if(s > ei || e < si) return 0;
    if(s >= si && e <= ei) return queryY(gap[n].lazy, 1, C, ssi, eei);
    ll lv = 0, rv = 0, m = s+e>>1;
    if(gap[n].lf != -1) lv = queryX(gap[n].lf, s, m, si, ei, ssi, eei);
    if(gap[n].rg != -1) rv = queryX(gap[n].rg, m+1, e, si, ei, ssi, eei);
    return _gcd(lv, rv);
}

void updateY(int now, int s, int e, int si, int ei, ll v) {
    if(s > ei || e < si) return;
    if(s >= si && e <= ei) { gap[now].gap = v; return; }
    if(gap[now].lazy == -1) {
        gap[now].lazy = si; gap[now].gap = v; return;
    } else {
        int m = s+e>>1;
        if(gap[now].lazy != -2) {
            if(gap[now].lazy <= m) {
                if(gap[now].lf == -1) gap[now].lf = gapcnt++;
                updateY(gap[now].lf, s, m, gap[now].lazy, gap[now].lazy, gap[now].gap);
            } else {
                if(gap[now].rg == -1) gap[now].rg = gapcnt++;
                updateY(gap[now].rg, m+1, e, gap[now].lazy, gap[now].lazy, gap[now].gap);
            }
        }

        if(si <= m) {
            if(gap[now].lf == -1) gap[now].lf = gapcnt++;
            updateY(gap[now].lf, s, m, si, ei, v);
        } else {
            if(gap[now].rg == -1) gap[now].rg = gapcnt++;
            updateY(gap[now].rg, m+1, e, si, ei, v);
        }

        ll lv = gap[now].lf == -1 ? 0 : gap[gap[now].lf].gap, rv = gap[now].rg == -1 ? 0 : gap[gap[now].rg].gap;
        gap[now].gap = _gcd(lv, rv);
        gap[now].lazy = -2;
    }
}

void updateX(int now, int s, int e, int si, int ei, int v, ll z) {
    if(s > ei || e < si) return;
    if(gap[now].lazy < 0) gap[now].lazy = gapcnt++;
    if(s >= si && e <= ei) { updateY(gap[now].lazy, 1, C, v, v, z); return; }
    int m = s+e>>1;
    ll lv = 0, rv = 0;
    if(si <= m) {
        if(gap[now].lf == -1) gap[now].lf = gapcnt++;
        updateX(gap[now].lf, s, m, si, ei, v, z); lv = z;
    } else {
        if(gap[now].rg == -1) gap[now].rg = gapcnt++;
        updateX(gap[now].rg, m+1, e, si, ei, v, z); rv = z;
    }
    lv = (lv == 0 && gap[now].lf < 0) ? 0 : queryY(gap[gap[now].lf].lazy, 1, C, v, v);
    rv = (rv == 0 && gap[now].rg < 0) ? 0 : queryY(gap[gap[now].rg].lazy, 1, C, v, v);
    updateY(gap[now].lazy, 1, C, v, v, _gcd(lv, rv));
}

void init(int _R, int _C) {
    gapcnt = 1; R = _R, C = _C;
}
void update(int P, int Q, ll K) {
    ++P; ++Q;
    updateX(0, 1, R, P, P, Q, K);
    if(gapcnt > 10000000) exit(1);
}

ll calculate(int P, int Q, int U, int V) {
    ++P; ++Q; ++U; ++V;
    return queryX(0, 1, R, P, U, Q, V);
}

Compilation message (stderr)

game.cpp: In function 'll queryY(int, int, int, int, int)':
game.cpp:22:38: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   22 |     ll lv = 0, rv = 0, ret = 0, m = s+e>>1;
      |                                     ~^~
game.cpp: In function 'll queryX(int, int, int, int, int, int, int)':
game.cpp:31:29: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   31 |     ll lv = 0, rv = 0, m = s+e>>1;
      |                            ~^~
game.cpp: In function 'void updateY(int, int, int, int, int, ll)':
game.cpp:43:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   43 |         int m = s+e>>1;
      |                 ~^~
game.cpp: In function 'void updateX(int, int, int, int, int, int, ll)':
game.cpp:72:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   72 |     int m = s+e>>1;
      |             ~^~

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