Competitive Programming

IOI 2013 - Game

Given a 2D grid of size R C (up to 10^9 10^9), support two operations: Update (r, c, v): Set the value at cell (r, c) to v. Query (r_1, c_1, r_2, c_2): Return the GCD of all values in the rectangle [r_1, r_2] [c_1, c_...

Source sync Apr 19, 2026

Track IOI

Year 2013

Files TeX and C++

Folder competitive_programming/ioi/2013/game

IOI2013TeXC++

This page is built from the copied files in competitive_programming/ioi/2013/game. Edit competitive_programming/ioi/2013/game/solution.tex to update the written solution and competitive_programming/ioi/2013/game/solution.cpp to update the implementation.

The website does not replace those files with hand-maintained HTML. It reads the copied source tree during the build and exposes the exact files below.

Raw TeX Raw C++

Problem statement

Problem Statement

Rendered from the "Problem Summary" section inside solution.tex because this entry has no separate statement file.

Raw TeX

Given a 2D grid of size $R \times C$ (up to $10^9 \times 10^9$), support two operations:

Update$(r, c, v)$: Set the value at cell $(r, c)$ to $v$.
Query$(r_1, c_1, r_2, c_2)$: Return the GCD of all values in the rectangle $[r_1, r_2] \times [c_1, c_2]$.
Initially, all cells are 0 (and $\gcd(0, x) = x$). There are up to $Q = 22000$ operations.

Editorial

Rendered from the copied solution.tex file. The original TeX source remains available below.

Raw TeX

Solution Approach

Since the grid is huge ($10^9 \times 10^9$) but the number of operations is small ($Q \leq 22000$), we need a dynamic 2D segment tree (segment tree of segment trees) with nodes created on demand.

Structure:

The outer segment tree is on rows (range $[0, R-1]$).
Each node of the outer tree contains an inner segment tree on columns (range $[0, C-1]$).
Both trees are dynamic (implicit): nodes are only created when needed.
Operations:

Update: Update the inner tree at the leaf node for row $r$, then propagate up, updating inner trees at ancestor nodes.
Query: Traverse the outer tree for the row range, and for each relevant node, query its inner tree for the column range. Combine results with GCD.

Complexity

Time per operation: $O(\log R \cdot \log C)$
Space: $O(Q \cdot \log R \cdot \log C)$

C++ Solution

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll gcd(ll a, ll b){
    while(b){ a %= b; swap(a, b); }
    return a;
}

// Inner segment tree (on columns), dynamic
struct InnerNode {
    ll val;
    int left, right; // children indices
};

vector<InnerNode> innerPool;
int newInnerNode(){
    innerPool.push_back({0, -1, -1});
    return (int)innerPool.size() - 1;
}

void innerUpdate(int node, int lo, int hi, int pos, ll val){
    if(lo == hi){
        innerPool[node].val = val;
        return;
    }
    int mid = lo + (hi - lo) / 2;
    if(pos <= mid){
        if(innerPool[node].left == -1)
            innerPool[node].left = newInnerNode();
        innerUpdate(innerPool[node].left, lo, mid, pos, val);
    } else {
        if(innerPool[node].right == -1)
            innerPool[node].right = newInnerNode();
        innerUpdate(innerPool[node].right, mid+1, hi, pos, val);
    }
    ll lv = (innerPool[node].left == -1) ? 0 : innerPool[innerPool[node].left].val;
    ll rv = (innerPool[node].right == -1) ? 0 : innerPool[innerPool[node].right].val;
    innerPool[node].val = gcd(lv, rv);
}

ll innerQuery(int node, int lo, int hi, int ql, int qr){
    if(node == -1 || lo > qr || hi < ql) return 0;
    if(ql <= lo && hi <= qr) return innerPool[node].val;
    int mid = lo + (hi - lo) / 2;
    return gcd(innerQuery(innerPool[node].left, lo, mid, ql, qr),
               innerQuery(innerPool[node].right, mid+1, hi, ql, qr));
}

// Outer segment tree (on rows), dynamic
struct OuterNode {
    int innerRoot; // root of inner segment tree
    int left, right; // children indices
};

vector<OuterNode> outerPool;
int newOuterNode(){
    outerPool.push_back({newInnerNode(), -1, -1});
    return (int)outerPool.size() - 1;
}

int R, C;

void outerUpdate(int node, int lo, int hi, int row, int col, ll val){
    if(lo == hi){
        innerUpdate(outerPool[node].innerRoot, 0, C-1, col, val);
        return;
    }
    int mid = lo + (hi - lo) / 2;
    if(row <= mid){
        if(outerPool[node].left == -1)
            outerPool[node].left = newOuterNode();
        outerUpdate(outerPool[node].left, lo, mid, row, col, val);
    } else {
        if(outerPool[node].right == -1)
            outerPool[node].right = newOuterNode();
        outerUpdate(outerPool[node].right, mid+1, hi, row, col, val);
    }
    // Merge children's inner trees at this node
    ll lv = (outerPool[node].left == -1) ? 0 :
        innerQuery(outerPool[outerPool[node].left].innerRoot, 0, C-1, col, col);
    ll rv = (outerPool[node].right == -1) ? 0 :
        innerQuery(outerPool[outerPool[node].right].innerRoot, 0, C-1, col, col);
    innerUpdate(outerPool[node].innerRoot, 0, C-1, col, gcd(lv, rv));
}

ll outerQuery(int node, int lo, int hi, int r1, int r2, int c1, int c2){
    if(node == -1 || lo > r2 || hi < r1) return 0;
    if(r1 <= lo && hi <= r2){
        return innerQuery(outerPool[node].innerRoot, 0, C-1, c1, c2);
    }
    int mid = lo + (hi - lo) / 2;
    return gcd(outerQuery(outerPool[node].left, lo, mid, r1, r2, c1, c2),
               outerQuery(outerPool[node].right, mid+1, hi, r1, r2, c1, c2));
}

void init(int r, int c){
    R = r; C = c;
    innerPool.clear();
    outerPool.clear();
    innerPool.reserve(5000000);
    outerPool.reserve(500000);
    newOuterNode(); // root = 0
}

void update(int r, int c, ll val){
    outerUpdate(0, 0, R-1, r, c, val);
}

ll calculate(int r1, int c1, int r2, int c2){
    return outerQuery(0, 0, R-1, r1, r2, c1, c2);
}

int main(){
    int r, c, n;
    cin >> r >> c >> n;
    init(r, c);

    for(int i = 0; i < n; i++){
        int type;
        cin >> type;
        if(type == 1){
            int pr, pc;
            ll val;
            cin >> pr >> pc >> val;
            update(pr, pc, val);
        } else {
            int r1, c1, r2, c2;
            cin >> r1 >> c1 >> r2 >> c2;
            cout << calculate(r1, c1, r2, c2) << "\n";
        }
    }

    return 0;
}

C++ competitive_programming/ioi/2013/game/solution.cpp

Exact copied implementation source.

Raw file

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll gcd(ll a, ll b){
    while(b){ a %= b; swap(a, b); }
    return a;
}

// Inner segment tree (on columns), dynamic
struct InnerNode {
    ll val;
    int left, right; // children indices
};

vector<InnerNode> innerPool;
int newInnerNode(){
    innerPool.push_back({0, -1, -1});
    return (int)innerPool.size() - 1;
}

void innerUpdate(int node, int lo, int hi, int pos, ll val){
    if(lo == hi){
        innerPool[node].val = val;
        return;
    }
    int mid = lo + (hi - lo) / 2;
    if(pos <= mid){
        if(innerPool[node].left == -1)
            innerPool[node].left = newInnerNode();
        innerUpdate(innerPool[node].left, lo, mid, pos, val);
    } else {
        if(innerPool[node].right == -1)
            innerPool[node].right = newInnerNode();
        innerUpdate(innerPool[node].right, mid+1, hi, pos, val);
    }
    ll lv = (innerPool[node].left == -1) ? 0 : innerPool[innerPool[node].left].val;
    ll rv = (innerPool[node].right == -1) ? 0 : innerPool[innerPool[node].right].val;
    innerPool[node].val = gcd(lv, rv);
}

ll innerQuery(int node, int lo, int hi, int ql, int qr){
    if(node == -1 || lo > qr || hi < ql) return 0;
    if(ql <= lo && hi <= qr) return innerPool[node].val;
    int mid = lo + (hi - lo) / 2;
    return gcd(innerQuery(innerPool[node].left, lo, mid, ql, qr),
               innerQuery(innerPool[node].right, mid+1, hi, ql, qr));
}

// Outer segment tree (on rows), dynamic
struct OuterNode {
    int innerRoot; // root of inner segment tree
    int left, right; // children indices
};

vector<OuterNode> outerPool;
int newOuterNode(){
    outerPool.push_back({newInnerNode(), -1, -1});
    return (int)outerPool.size() - 1;
}

int R, C;

void outerUpdate(int node, int lo, int hi, int row, int col, ll val){
    if(lo == hi){
        innerUpdate(outerPool[node].innerRoot, 0, C-1, col, val);
        return;
    }
    int mid = lo + (hi - lo) / 2;
    if(row <= mid){
        if(outerPool[node].left == -1)
            outerPool[node].left = newOuterNode();
        outerUpdate(outerPool[node].left, lo, mid, row, col, val);
    } else {
        if(outerPool[node].right == -1)
            outerPool[node].right = newOuterNode();
        outerUpdate(outerPool[node].right, mid+1, hi, row, col, val);
    }
    // Merge children's inner trees at this node
    ll lv = (outerPool[node].left == -1) ? 0 :
        innerQuery(outerPool[outerPool[node].left].innerRoot, 0, C-1, col, col);
    ll rv = (outerPool[node].right == -1) ? 0 :
        innerQuery(outerPool[outerPool[node].right].innerRoot, 0, C-1, col, col);
    innerUpdate(outerPool[node].innerRoot, 0, C-1, col, gcd(lv, rv));
}

ll outerQuery(int node, int lo, int hi, int r1, int r2, int c1, int c2){
    if(node == -1 || lo > r2 || hi < r1) return 0;
    if(r1 <= lo && hi <= r2){
        return innerQuery(outerPool[node].innerRoot, 0, C-1, c1, c2);
    }
    int mid = lo + (hi - lo) / 2;
    return gcd(outerQuery(outerPool[node].left, lo, mid, r1, r2, c1, c2),
               outerQuery(outerPool[node].right, mid+1, hi, r1, r2, c1, c2));
}

void init(int r, int c){
    R = r; C = c;
    innerPool.clear();
    outerPool.clear();
    innerPool.reserve(5000000);
    outerPool.reserve(500000);
    newOuterNode(); // root = 0
}

void update(int r, int c, ll val){
    outerUpdate(0, 0, R-1, r, c, val);
}

ll calculate(int r1, int c1, int r2, int c2){
    return outerQuery(0, 0, R-1, r1, r2, c1, c2);
}

int main(){
    int r, c, n;
    cin >> r >> c >> n;
    init(r, c);

    for(int i = 0; i < n; i++){
        int type;
        cin >> type;
        if(type == 1){
            int pr, pc;
            ll val;
            cin >> pr >> pc >> val;
            update(pr, pc, val);
        } else {
            int r1, c1, r2, c2;
            cin >> r1 >> c1 >> r2 >> c2;
            cout << calculate(r1, c1, r2, c2) << "\n";
        }
    }

    return 0;
}

TeX write-up competitive_programming/ioi/2013/game/solution.tex

Exact copied write-up source.

Raw file

\documentclass[11pt,a4paper]{article}
\usepackage[utf8]{inputenc}
\usepackage[margin=1in]{geometry}
\usepackage{amsmath,amssymb,amsthm}
\usepackage{listings}
\usepackage{xcolor}
\usepackage{hyperref}

\lstset{
  language=C++,
  basicstyle=\ttfamily\small,
  keywordstyle=\color{blue}\bfseries,
  commentstyle=\color{green!60!black},
  stringstyle=\color{red!70!black},
  numbers=left,
  numberstyle=\tiny\color{gray},
  breaklines=true,
  frame=single,
  tabsize=4,
  showstringspaces=false
}

\title{IOI 2013 -- Game}
\author{Solution}
\date{}

\begin{document}
\maketitle

\section{Problem Summary}
Given a 2D grid of size $R \times C$ (up to $10^9 \times 10^9$), support two operations:
\begin{enumerate}
    \item \textbf{Update}$(r, c, v)$: Set the value at cell $(r, c)$ to $v$.
    \item \textbf{Query}$(r_1, c_1, r_2, c_2)$: Return the GCD of all values in the rectangle $[r_1, r_2] \times [c_1, c_2]$.
\end{enumerate}

Initially, all cells are 0 (and $\gcd(0, x) = x$). There are up to $Q = 22000$ operations.

\section{Solution Approach}
Since the grid is huge ($10^9 \times 10^9$) but the number of operations is small ($Q \leq 22000$), we need a \textbf{dynamic 2D segment tree} (segment tree of segment trees) with nodes created on demand.

\textbf{Structure:}
\begin{itemize}
    \item The outer segment tree is on rows (range $[0, R-1]$).
    \item Each node of the outer tree contains an inner segment tree on columns (range $[0, C-1]$).
    \item Both trees are dynamic (implicit): nodes are only created when needed.
\end{itemize}

\textbf{Operations:}
\begin{itemize}
    \item \textbf{Update:} Update the inner tree at the leaf node for row $r$, then propagate up, updating inner trees at ancestor nodes.
    \item \textbf{Query:} Traverse the outer tree for the row range, and for each relevant node, query its inner tree for the column range. Combine results with GCD.
\end{itemize}

\section{Complexity}
\begin{itemize}
    \item \textbf{Time per operation:} $O(\log R \cdot \log C)$
    \item \textbf{Space:} $O(Q \cdot \log R \cdot \log C)$
\end{itemize}

\section{C++ Solution}
\begin{lstlisting}
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll gcd(ll a, ll b){
    while(b){ a %= b; swap(a, b); }
    return a;
}

// Inner segment tree (on columns), dynamic
struct InnerNode {
    ll val;
    int left, right; // children indices
};

vector<InnerNode> innerPool;
int newInnerNode(){
    innerPool.push_back({0, -1, -1});
    return (int)innerPool.size() - 1;
}

void innerUpdate(int node, int lo, int hi, int pos, ll val){
    if(lo == hi){
        innerPool[node].val = val;
        return;
    }
    int mid = lo + (hi - lo) / 2;
    if(pos <= mid){
        if(innerPool[node].left == -1)
            innerPool[node].left = newInnerNode();
        innerUpdate(innerPool[node].left, lo, mid, pos, val);
    } else {
        if(innerPool[node].right == -1)
            innerPool[node].right = newInnerNode();
        innerUpdate(innerPool[node].right, mid+1, hi, pos, val);
    }
    ll lv = (innerPool[node].left == -1) ? 0 : innerPool[innerPool[node].left].val;
    ll rv = (innerPool[node].right == -1) ? 0 : innerPool[innerPool[node].right].val;
    innerPool[node].val = gcd(lv, rv);
}

ll innerQuery(int node, int lo, int hi, int ql, int qr){
    if(node == -1 || lo > qr || hi < ql) return 0;
    if(ql <= lo && hi <= qr) return innerPool[node].val;
    int mid = lo + (hi - lo) / 2;
    return gcd(innerQuery(innerPool[node].left, lo, mid, ql, qr),
               innerQuery(innerPool[node].right, mid+1, hi, ql, qr));
}

// Outer segment tree (on rows), dynamic
struct OuterNode {
    int innerRoot; // root of inner segment tree
    int left, right; // children indices
};

vector<OuterNode> outerPool;
int newOuterNode(){
    outerPool.push_back({newInnerNode(), -1, -1});
    return (int)outerPool.size() - 1;
}

int R, C;

void outerUpdate(int node, int lo, int hi, int row, int col, ll val){
    if(lo == hi){
        innerUpdate(outerPool[node].innerRoot, 0, C-1, col, val);
        return;
    }
    int mid = lo + (hi - lo) / 2;
    if(row <= mid){
        if(outerPool[node].left == -1)
            outerPool[node].left = newOuterNode();
        outerUpdate(outerPool[node].left, lo, mid, row, col, val);
    } else {
        if(outerPool[node].right == -1)
            outerPool[node].right = newOuterNode();
        outerUpdate(outerPool[node].right, mid+1, hi, row, col, val);
    }
    // Merge children's inner trees at this node
    ll lv = (outerPool[node].left == -1) ? 0 :
        innerQuery(outerPool[outerPool[node].left].innerRoot, 0, C-1, col, col);
    ll rv = (outerPool[node].right == -1) ? 0 :
        innerQuery(outerPool[outerPool[node].right].innerRoot, 0, C-1, col, col);
    innerUpdate(outerPool[node].innerRoot, 0, C-1, col, gcd(lv, rv));
}

ll outerQuery(int node, int lo, int hi, int r1, int r2, int c1, int c2){
    if(node == -1 || lo > r2 || hi < r1) return 0;
    if(r1 <= lo && hi <= r2){
        return innerQuery(outerPool[node].innerRoot, 0, C-1, c1, c2);
    }
    int mid = lo + (hi - lo) / 2;
    return gcd(outerQuery(outerPool[node].left, lo, mid, r1, r2, c1, c2),
               outerQuery(outerPool[node].right, mid+1, hi, r1, r2, c1, c2));
}

void init(int r, int c){
    R = r; C = c;
    innerPool.clear();
    outerPool.clear();
    innerPool.reserve(5000000);
    outerPool.reserve(500000);
    newOuterNode(); // root = 0
}

void update(int r, int c, ll val){
    outerUpdate(0, 0, R-1, r, c, val);
}

ll calculate(int r1, int c1, int r2, int c2){
    return outerQuery(0, 0, R-1, r1, r2, c1, c2);
}

int main(){
    int r, c, n;
    cin >> r >> c >> n;
    init(r, c);

    for(int i = 0; i < n; i++){
        int type;
        cin >> type;
        if(type == 1){
            int pr, pc;
            ll val;
            cin >> pr >> pc >> val;
            update(pr, pc, val);
        } else {
            int r1, c1, r2, c2;
            cin >> r1 >> c1 >> r2 >> c2;
            cout << calculate(r1, c1, r2, c2) << "\n";
        }
    }

    return 0;
}
\end{lstlisting}

\end{document}

C++ implementation competitive_programming/ioi/2013/game/solution.cpp

Exact copied implementation source.

Raw file

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll gcd(ll a, ll b){
    while(b){ a %= b; swap(a, b); }
    return a;
}

// Inner segment tree (on columns), dynamic
struct InnerNode {
    ll val;
    int left, right; // children indices
};

vector<InnerNode> innerPool;
int newInnerNode(){
    innerPool.push_back({0, -1, -1});
    return (int)innerPool.size() - 1;
}

void innerUpdate(int node, int lo, int hi, int pos, ll val){
    if(lo == hi){
        innerPool[node].val = val;
        return;
    }
    int mid = lo + (hi - lo) / 2;
    if(pos <= mid){
        if(innerPool[node].left == -1)
            innerPool[node].left = newInnerNode();
        innerUpdate(innerPool[node].left, lo, mid, pos, val);
    } else {
        if(innerPool[node].right == -1)
            innerPool[node].right = newInnerNode();
        innerUpdate(innerPool[node].right, mid+1, hi, pos, val);
    }
    ll lv = (innerPool[node].left == -1) ? 0 : innerPool[innerPool[node].left].val;
    ll rv = (innerPool[node].right == -1) ? 0 : innerPool[innerPool[node].right].val;
    innerPool[node].val = gcd(lv, rv);
}

ll innerQuery(int node, int lo, int hi, int ql, int qr){
    if(node == -1 || lo > qr || hi < ql) return 0;
    if(ql <= lo && hi <= qr) return innerPool[node].val;
    int mid = lo + (hi - lo) / 2;
    return gcd(innerQuery(innerPool[node].left, lo, mid, ql, qr),
               innerQuery(innerPool[node].right, mid+1, hi, ql, qr));
}

// Outer segment tree (on rows), dynamic
struct OuterNode {
    int innerRoot; // root of inner segment tree
    int left, right; // children indices
};

vector<OuterNode> outerPool;
int newOuterNode(){
    outerPool.push_back({newInnerNode(), -1, -1});
    return (int)outerPool.size() - 1;
}

int R, C;

void outerUpdate(int node, int lo, int hi, int row, int col, ll val){
    if(lo == hi){
        innerUpdate(outerPool[node].innerRoot, 0, C-1, col, val);
        return;
    }
    int mid = lo + (hi - lo) / 2;
    if(row <= mid){
        if(outerPool[node].left == -1)
            outerPool[node].left = newOuterNode();
        outerUpdate(outerPool[node].left, lo, mid, row, col, val);
    } else {
        if(outerPool[node].right == -1)
            outerPool[node].right = newOuterNode();
        outerUpdate(outerPool[node].right, mid+1, hi, row, col, val);
    }
    // Merge children's inner trees at this node
    ll lv = (outerPool[node].left == -1) ? 0 :
        innerQuery(outerPool[outerPool[node].left].innerRoot, 0, C-1, col, col);
    ll rv = (outerPool[node].right == -1) ? 0 :
        innerQuery(outerPool[outerPool[node].right].innerRoot, 0, C-1, col, col);
    innerUpdate(outerPool[node].innerRoot, 0, C-1, col, gcd(lv, rv));
}

ll outerQuery(int node, int lo, int hi, int r1, int r2, int c1, int c2){
    if(node == -1 || lo > r2 || hi < r1) return 0;
    if(r1 <= lo && hi <= r2){
        return innerQuery(outerPool[node].innerRoot, 0, C-1, c1, c2);
    }
    int mid = lo + (hi - lo) / 2;
    return gcd(outerQuery(outerPool[node].left, lo, mid, r1, r2, c1, c2),
               outerQuery(outerPool[node].right, mid+1, hi, r1, r2, c1, c2));
}

void init(int r, int c){
    R = r; C = c;
    innerPool.clear();
    outerPool.clear();
    innerPool.reserve(5000000);
    outerPool.reserve(500000);
    newOuterNode(); // root = 0
}

void update(int r, int c, ll val){
    outerUpdate(0, 0, R-1, r, c, val);
}

ll calculate(int r1, int c1, int r2, int c2){
    return outerQuery(0, 0, R-1, r1, r2, c1, c2);
}

int main(){
    int r, c, n;
    cin >> r >> c >> n;
    init(r, c);

    for(int i = 0; i < n; i++){
        int type;
        cin >> type;
        if(type == 1){
            int pr, pc;
            ll val;
            cin >> pr >> pc >> val;
            update(pr, pc, val);
        } else {
            int r1, c1, r2, c2;
            cin >> r1 >> c1 >> r2 >> c2;
            cout << calculate(r1, c1, r2, c2) << "\n";
        }
    }

    return 0;
}

IOI 2013 - Game

Source-first archive entry

Problem Statement

Editorial

Solution Approach

Complexity

C++ Solution

Code

Source Files