Submission #573179

#	Time	Username	Problem	Language	Result	Execution time	Memory
573179		Theo830	Game (IOI13_game)	C++17	10 / 100	1403 ms	256000 KiB

game

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll INF = 1e9+7;
const ll MOD = 998244353;
typedef pair<ll,ll> ii;
#define iii pair<ll,ii>
#define ull unsigned ll
#define f(i,a,b) for(ll i = a;i < b;i++)
#define pb push_back
#define vll vector<ll>
#define F first
#define S second
#define all(x) (x).begin(), (x).end()
///I hope I will get uprating and don't make mistakes
///I will never stop programming
///sqrt(-1) Love C++
///Please don't hack me
///@TheofanisOrfanou Theo830
///Think different approaches (bs,dp,greedy,graphs,shortest paths,mst)
///Stay Calm
///Look for special cases
///Beware of overflow and array bounds
///Think the problem backwards
///Training
#include "game.h"
struct node_y{
    ll val = 0;
};
struct sp{
    ll l = -1,r = -1;
};
vector<sp>py;
struct node_x{
    ll l = -1,r = -1;
    vector<node_y>seg_y;
};
vector<node_x>seg(1);
ll cx = 1,cy = 1;
ll N,M;
ll em = 10000;
void init(int R, int C){
    node_y a;
    seg[0].seg_y.assign(em,a);
    sp A;
    py.assign(em,A);
    N = R;
    M = C;
}
void upd_y(ll lx,ll rx,ll curx,ll ly,ll ry,ll cury,ll X,ll Y,ll val){
    if(ly == ry){
        if(lx == rx){
            seg[curx].seg_y[cury].val = val;
        }
        else{
            seg[curx].seg_y[cury].val = 0;
            if(seg[curx].l != -1){
                ll pos = seg[seg[curx].l].seg_y[cury].val;
                seg[curx].seg_y[cury].val = __gcd(seg[curx].seg_y[cury].val,pos);
            }
            if(seg[curx].r != -1){
                ll pos = seg[seg[curx].r].seg_y[cury].val;
                seg[curx].seg_y[cury].val = __gcd(seg[curx].seg_y[cury].val,pos);
            }
        }
    }
    else{
        ll mid = (ly+ry)/2;
        if(Y <= mid){
            if(py[cury].l == -1){
                py[cury].l = cy;
                cy++;
            }
            upd_y(lx,rx,curx,ly,mid,py[cury].l,X,Y,val);
        }
        else{
            if(py[cury].r == -1){
                py[cury].r = cy;
                cy++;
            }
            upd_y(lx,rx,curx,mid+1,ry,py[cury].r,X,Y,val);
        }
        seg[curx].seg_y[cury].val = 0;
        if(py[cury].l != -1){
            ll pos = py[cury].l;
            seg[curx].seg_y[cury].val = __gcd(seg[curx].seg_y[cury].val,seg[curx].seg_y[pos].val);
        }
        if(py[cury].r != -1){
            ll pos = py[cury].r;
            seg[curx].seg_y[cury].val = __gcd(seg[curx].seg_y[cury].val,seg[curx].seg_y[pos].val);
        }
    }
}
void upd_x(ll lx,ll rx,ll curx,ll X,ll Y,ll val){
    if(lx != rx){
        ll mid = (lx + rx) / 2;
        if(X <= mid){
            if(seg[curx].l == -1){
                seg[curx].l = cx;
                cx++;
                node_x neo;
                node_y a;
                neo.seg_y.assign(em,a);
                seg.pb(neo);
            }
            upd_x(lx,mid,seg[curx].l,X,Y,val);
        }
        else{
            if(seg[curx].r == -1){
                seg[curx].r = cx;
                cx++;
                node_x neo;
                node_y a;
                neo.seg_y.assign(em,a);
                seg.pb(neo);
            }
            upd_x(mid+1,rx,seg[curx].r,X,Y,val);
        }
    }
    upd_y(lx,rx,curx,0,M-1,0,X,Y,val);
}
ll ask_y(ll lx,ll rx,ll curx,ll ly,ll ry,ll cury,ll X1,ll X2,ll Y1,ll Y2){
    if(Y1 <= ly && ry <= Y2){
        return seg[curx].seg_y[cury].val;
    }
    if(ly > Y2 || Y1 > ry){
        return 0;
    }
    ll ans = 0;
    ll mid = (ly + ry) / 2;
    if(py[cury].l != -1){
        ans = __gcd(ans,ask_y(lx,rx,curx,ly,mid,py[cury].l,X1,X2,Y1,Y2));
    }
    if(py[cury].r != -1){
        ans = __gcd(ans,ask_y(lx,rx,curx,mid+1,ry,py[cury].r,X1,X2,Y1,Y2));
    }
    return ans;
}
ll ask_x(ll lx,ll rx,ll curx,ll X1,ll X2,ll Y1,ll Y2){
    if(X1 <= lx && rx <= X2){
        return ask_y(lx,rx,curx,0,M-1,0,X1,X2,Y1,Y2);
    }
    if(lx > X2 || X1 > rx){
        return 0;
    }
    ll ans = 0;
    ll mid = (lx + rx) / 2;
    if(seg[curx].l != -1){
        ans = __gcd(ans,ask_x(lx,mid,seg[curx].l,X1,X2,Y1,Y2));
    }
    if(seg[curx].r != -1){
        ans = __gcd(ans,ask_x(mid+1,rx,seg[curx].r,X1,X2,Y1,Y2));
    }
    return ans;
}
void update(int P, int Q, long long K) {
    upd_x(0,N-1,0,P,Q,K);
}
long long calculate(int P, int Q, int U, int V) {
    return ask_x(0,N-1,0,P,U,Q,V);
}
/*
#define MAX_SIZE 1000000000
#define MAX_N 272000

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
	int R, C, N;
    int P, Q, U, V;
    long long K;
    int i, type;
	int res;

	res = scanf("%d", &R);
	res = scanf("%d", &C);
	res = scanf("%d", &N);

    init(R, C);
	for (i = 0; i < N; i++) {
        res = scanf("%d", &type);
        if (type == 1) {
		    res = scanf("%d%d%lld", &P, &Q, &K);
            update(P, Q, K);
        } else if (type == 2) {
		    res = scanf("%d%d%d%d", &P, &Q, &U, &V);
            cout<<calculate(P, Q, U, V)<<"\n";
        }
	}

	return 0;
}



2 3 9
1 0 0 20
1 0 2 15
1 1 1 12
2 0 0 0 2
2 0 0 1 1
1 0 1 6
1 1 1 14
2 0 0 0 2
2 0 0 1 1
*/

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