Submission #1121453

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121453		Zero_OP	Game (IOI13_game)	C++14	100 / 100	3467 ms	139916 KiB

game

#ifndef LOCAL
    #include <game.h>
#endif // LOCAL

#include <bits/stdc++.h>

using namespace std;

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;
}

const int LMT = 5e6 + 5;

int N, M;

struct node{
    int ln, rn; long long x;
    int pos;

    node() : ln(0), rn(0), x(0), pos(-1) {}
} nodes[LMT];
int n_nodes = 0;

struct seg1D{
    int rt;

    seg1D() : rt(0) {}

    void update(int &id, int l, int r, int pos, long long x){
        if(!id){
            id = ++n_nodes;
            nodes[id].x = x;
            nodes[id].pos = pos;
            return;
        }

        if(l == r) nodes[id].x = x;
        else{
            int mid = l + r >> 1;
            if(nodes[id].pos != -1){
                if(nodes[id].pos <= mid) update(nodes[id].ln, l, mid, nodes[id].pos, nodes[id].x);
                else update(nodes[id].rn, mid + 1, r, nodes[id].pos, nodes[id].x);
                nodes[id].pos = -1;
            }

            if(pos <= mid) update(nodes[id].ln, l, mid, pos, x);
            else update(nodes[id].rn, mid + 1, r, pos, x);

            nodes[id].x = gcd2(nodes[nodes[id].ln].x, nodes[nodes[id].rn].x);
        }
    }

    long long query(int& id, int l, int r, int u, int v){
        if(v < l || u > r || !id) return 0ll;
        if(u <= l && r <= v) return nodes[id].x;

        int mid = l + r >> 1;
        if(nodes[id].pos != -1){
            return (u <= nodes[id].pos && nodes[id].pos <= v ? nodes[id].x : 0ll);
        }

        return gcd2(query(nodes[id].ln, l, mid, u, v), query(nodes[id].rn, mid + 1, r, u, v));
    }
};

struct node2D{
    seg1D rt;
    int ln, rn;
    node2D() : rt(), ln(0), rn(0) {}
} trs[22000 * 35];
int n_trees = 0;

struct seg2D{
    int rt;

    seg2D() : rt(0) {}

    void update(int& id, int l, int r, int x, int y, long long val){
        if(!id){
            id = ++n_trees;
            trs[id].rt.rt = ++n_nodes;
        }

        if(l == r) trs[id].rt.update(trs[id].rt.rt, 0, M - 1, y, val);
        else{
            int mid = l + r >> 1;
            if(x <= mid) update(trs[id].ln, l, mid, x, y, val);
            else update(trs[id].rn, mid + 1, r, x, y, val);

            val = gcd2(trs[trs[id].ln].rt.query(trs[trs[id].ln].rt.rt, 0, M - 1, y, y),
                       trs[trs[id].rn].rt.query(trs[trs[id].rn].rt.rt, 0, M - 1, y, y));
            trs[id].rt.update(trs[id].rt.rt, 0, M - 1, y, val);
        }
    }

    long long query(int id, int l, int r, int u, int v, int u2, int v2){
        if(v < l || u > r || id == 0) return 0;
        if(u <= l && r <= v) return trs[id].rt.query(trs[id].rt.rt, 0, M - 1, u2, v2);
        int mid = l + r >> 1;
        return gcd2(query(trs[id].ln, l, mid, u, v, u2, v2), query(trs[id].rn, mid + 1, r, u, v, u2, v2));
    }
} T;

void init(int R, int C){
    N = R;
    M = C;
}

void update(int R, int C, long long val){
    T.update(T.rt, 0, N - 1, R, C, val);
}

long long calculate(int x1, int y1, int x2, int y2){
    return T.query(T.rt, 0, N - 1, x1, x2, y1, y2);
}

#ifdef LOCAL
int main(){
    ios_base::sync_with_stdio(0); cin.tie(0);

    freopen("task.inp", "r", stdin);
    freopen("task.out", "w", stdout);

    int R, C, N;
    cin >> R >> C >> N;

    init(R, C);

    while(N--){
        int type;
        cin >> type;
        if(type == 1){
            int x, y; long long val;
            cin >> x >> y >> val;
            update(x, y, val);
        } else{
            int x1, y1, x2, y2;
            cin >> x1 >> y1 >> x2 >> y2;
            cout << calculate(x1, y1, x2, y2) << '\n';
        }
    }

    return 0;
}
#endif //LOCAL

Compilation message (stderr)

game.cpp: In member function 'void seg1D::update(int&, int, int, int, long long int)':
game.cpp:46:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   46 |             int mid = l + r >> 1;
      |                       ~~^~~
game.cpp: In member function 'long long int seg1D::query(int&, int, int, int, int)':
game.cpp:64:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   64 |         int mid = l + r >> 1;
      |                   ~~^~~
game.cpp: In member function 'void seg2D::update(int&, int, int, int, int, long long int)':
game.cpp:93:25: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   93 |             int mid = l + r >> 1;
      |                       ~~^~~
game.cpp: In member function 'long long int seg2D::query(int, int, int, int, int, int, int)':
game.cpp:106:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
  106 |         int mid = l + r >> 1;
      |                   ~~^~~

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