Submission #1087609

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087609		Zero_OP	Game (IOI13_game)	C++17	80 / 100	2839 ms	256000 KiB

game

#ifndef LOCAL
#include "game.h"
#endif //LOCAL

#include <bits/stdc++.h>

using namespace std;

#define sz(v) (int)v.size()
#define all(v) begin(v), end(v)
#define compact(v) v.erase(unique(all(v)), end(v))
#define dbg(x) "[" #x " = " << (x) << "]"

template<typename T>
    bool minimize(T& a, const T& b){
        if(a > b) return a = b, true;
        return false;
    }

template<typename T>
    bool maximize(T& a, const T& b){
        if(a < b) return a = b, true;
        return false;
    }

using ll = long long;
using ld = long double;
using vi = vector<int>;
using vl = vector<ll>;


long long gcd2(long long X, long long Y) {
//    cout << X << ' ' << Y << '\n';
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

const int MAX = 1e7 + 5;
int N, M, tree2D, lt[MAX], rt[MAX], id[MAX], num;
long long st[MAX];

void define(int& x){
    if(x == 0) x = ++num;
}

void update_y(int& idx, int lx, int rx, int tl, int tr, int& idy, int ly, int ry, int y, long long k){
    define(idy);

    if(ly == ry){
        if(lx == rx) st[idy] = k;
        else st[idy] = gcd2(st[tl], st[tr]);
    } else{
        int mid = (ly + ry) >> 1;
        if(y <= mid) update_y(idx, lx, rx, lt[tl], lt[tr], lt[idy], ly, mid, y, k);
        else update_y(idx, lx, rx, rt[tl], rt[tr], rt[idy], mid + 1, ry, y, k);

        st[idy] = gcd2(st[lt[idy]], st[rt[idy]]);
    }
}

void update_x(int& idx, int lx, int rx, int x, int y, long long k){
    define(idx);

    if(lx < rx){
        int mid = lx + rx >> 1;
        if(x <= mid) update_x(lt[idx], lx, mid, x, y, k);
        else update_x(rt[idx], mid + 1, rx, x, y, k);
    }

    update_y(idx, lx, rx, id[lt[idx]], id[rt[idx]], id[idx], 0, M - 1, y, k);
}

long long query_y(int& idy, int ly, int ry, int u, int v){
    if((u <= ly && ry <= v) || idy == 0) return st[idy];
    int mid = ly + ry >> 1;
    long long g = 0;
    if(u <= mid) g = gcd2(g, query_y(lt[idy], ly, mid, u, v));
    if(mid < v) g = gcd2(g, query_y(rt[idy], mid + 1, ry, u, v));
    return g;
}

long long query_x(int& idx, int lx, int rx, int u, int v, int p, int q){
    if((u <= lx && rx <= v) || idx == 0) return query_y(id[idx], 0, M - 1, p, q);
     int mid = lx + rx >> 1;
     long long g = 0;
     if(u <= mid) g = gcd2(g, query_x(lt[idx], lx, mid, u, v, p, q));
     if(mid < v) g = gcd2(g, query_x(rt[idx], mid + 1, rx, u, v, p, q));
     return g;
}

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

void update(int P, int Q, long long K) {
    update_x(tree2D, 0, N - 1, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return query_x(tree2D, 0, N - 1, P, U, Q, V);
}


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

    #define filename "task"
    if(fopen(filename".inp", "r")){
        freopen(filename".inp", "r", stdin);
        freopen(filename".out", "w", stdout);
    }

    int Q;
    cin >> N >> M >> Q;

    init(N, M);

    while(Q--){
        int type;
        cin >> type;
        if(type == 1){
            int x, y; long long z;
            cin >> x >> y >> z;
            update(x, y, z);
        } else{
            int p, q, u, v;
            cin >> p >> q >> u >> v;
            cout << calculate(p, q, u, v) << '\n';
        }
    }


    return 0;
}
#endif // LOCAL

Compilation message (stderr)

game.cpp: In function 'void update_x(int&, int, int, int, int, long long int)':
game.cpp:70:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   70 |         int mid = lx + rx >> 1;
      |                   ~~~^~~~
game.cpp: In function 'long long int query_y(int&, int, int, int, int)':
game.cpp:80:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   80 |     int mid = ly + ry >> 1;
      |               ~~~^~~~
game.cpp: In function 'long long int query_x(int&, int, int, int, int, int, int)':
game.cpp:89:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   89 |      int mid = lx + rx >> 1;
      |                ~~~^~~~

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