Submission #706228

#	Time	Username	Problem	Language	Result	Execution time	Memory
706228		sharaelong	Game (IOI13_game)	C++17	100 / 100	4030 ms	102628 KiB

game

#include "game.h"
#include <bits/stdc++.h>
#ifdef SHARAELONG
#include "../../cpp-header/debug.hpp"
#endif
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;

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

struct Node1 {
    int n, ln, rn; // left node, right node
    Node1() : n(-1), ln(-1), rn(-1) {}
};

struct Node2 {
    int ln, rn, latest;
    ll val;
    Node2() : ln(-1), rn(-1), val(0), latest(-1) {}
};

int R, C;
vector<Node1> node1;
vector<Node2> node2;

int new_node1() {
    node1.push_back(Node1());
    return node1.size()-1;
}

int new_node2() {
    node2.push_back(Node2());
    return node2.size()-1;
}

void update2(int n, int nl, int nr, int y, ll v) {
    if (nl == nr) {
        node2[n].val = v;
        return;
    }

    int mid = (nl + nr) / 2;
    if (node2[n].latest != -1) {
        if (node2[n].latest <= mid) {
            node2[n].ln = new_node2();
            node2[node2[n].ln].latest = node2[n].latest;
            node2[node2[n].ln].val = node2[n].val;
        } else {
            node2[n].rn = new_node2();
            node2[node2[n].rn].latest = node2[n].latest;
            node2[node2[n].rn].val = node2[n].val;
        }
        node2[n].latest = -1;
    }
    
    if (y <= mid) {
        if (node2[n].ln == -1) {
            node2[n].ln = new_node2();
            node2[node2[n].ln].latest = y;
            node2[node2[n].ln].val = v;
        } else {
            update2(node2[n].ln, nl, mid, y, v);
        }
    } else {
        if (node2[n].rn == -1) {
            node2[n].rn = new_node2();
            node2[node2[n].rn].latest = y;
            node2[node2[n].rn].val = v;
        } else {
            update2(node2[n].rn, mid+1, nr, y, v);
        }
    }

    ll upd_gcd = 0;
    if (node2[n].ln != -1) upd_gcd = gcd2(upd_gcd, node2[node2[n].ln].val);
    if (node2[n].rn != -1) upd_gcd = gcd2(upd_gcd, node2[node2[n].rn].val);
    node2[n].val = upd_gcd;
}

ll query2(int n, int nl, int nr, int l, int r) {
    if (r < nl || nr < l) return 0;
    if (l <= nl && nr <= r) return node2[n].val;
    if (node2[n].latest != -1) {
        return (l <= node2[n].latest && node2[n].latest <= r ? node2[n].val : 0);
    }

    ll ret = 0;
    int mid = (nl + nr) / 2;
    if (node2[n].ln != -1) ret = gcd2(ret, query2(node2[n].ln, nl, mid, l, r));
    if (node2[n].rn != -1) ret = gcd2(ret, query2(node2[n].rn, mid+1, nr, l, r));
    return ret;
}

void update1(int n, int nl, int nr, int x, int y, ll v) {
    if (node1[n].n == -1) node1[n].n = new_node2();
    if (nl == nr) {
        update2(node1[n].n, 0, C-1, y, v);
        return;
    }

    int mid = (nl + nr) / 2;
    if (x <= mid) {
        if (node1[n].ln == -1) node1[n].ln = new_node1();
        update1(node1[n].ln, nl, mid, x, y, v);
    } else {
        if (node1[n].rn == -1) node1[n].rn = new_node1();
        update1(node1[n].rn, mid+1, nr, x, y, v);
    }

    ll upd_gcd = 0;
    if (node1[n].ln != -1) upd_gcd = gcd2(upd_gcd, query2(node1[node1[n].ln].n, 0, C-1, y, y));
    if (node1[n].rn != -1) upd_gcd = gcd2(upd_gcd, query2(node1[node1[n].rn].n, 0, C-1, y, y));
    update2(node1[n].n, 0, C-1, y, upd_gcd);
}

ll query1(int n, int nl, int nr, int x1, int y1, int x2, int y2) {
    if (nr < x1 || x2 < nl) return 0;
    if (x1 <= nl && nr <= x2) return (node1[n].n != -1 ? query2(node1[n].n, 0, C-1, y1, y2) : 0);

    ll ret = 0;
    int mid = (nl + nr) / 2;
    if (node1[n].ln != -1) ret = gcd2(ret, query1(node1[n].ln, nl, mid, x1, y1, x2, y2));
    if (node1[n].rn != -1) ret = gcd2(ret, query1(node1[n].rn, mid+1, nr, x1, y1, x2, y2));
    return ret;
}


int root;

void init(int _R, int _C) {
    R = _R;
    C = _C;
    root = new_node1();
}

void update(int P, int Q, ll K) {
    update1(root, 0, R-1, P, Q, K);
}

ll calculate(int P, int Q, int U, int V) {
    return query1(root, 0, R-1, P, Q, U, V);
}

Compilation message (stderr)

game.cpp: In constructor 'Node2::Node2()':
game.cpp:27:8: warning: 'Node2::val' will be initialized after [-Wreorder]
   27 |     ll val;
      |        ^~~
game.cpp:26:17: warning:   'int Node2::latest' [-Wreorder]
   26 |     int ln, rn, latest;
      |                 ^~~~~~
game.cpp:28:5: warning:   when initialized here [-Wreorder]
   28 |     Node2() : ln(-1), rn(-1), val(0), latest(-1) {}
      |     ^~~~~

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