oj.uz

Submission #573184

# Submission time Handle Problem Language Result Execution time Memory
573184 2022-06-06T08:34:02 Z Theo830 Game (IOI13_game) C++17
37 / 100
 659 ms 256000 KB 
#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 = 100000;
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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2644 KB Output is correct
2 Correct 75 ms 123996 KB Output is correct
3 Correct 61 ms 124720 KB Output is correct
4 Correct 3 ms 4964 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 57 ms 123960 KB Output is correct
7 Correct 4 ms 7364 KB Output is correct
8 Correct 9 ms 16708 KB Output is correct
9 Correct 55 ms 119216 KB Output is correct
10 Correct 35 ms 77720 KB Output is correct
11 Correct 13 ms 26052 KB Output is correct
12 Correct 3 ms 4932 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 3 ms 4932 KB Output is correct
3 Correct 4 ms 7364 KB Output is correct
4 Correct 617 ms 22272 KB Output is correct
5 Correct 449 ms 22668 KB Output is correct
6 Correct 477 ms 18652 KB Output is correct
7 Correct 486 ms 18328 KB Output is correct
8 Correct 350 ms 19148 KB Output is correct
9 Correct 567 ms 18408 KB Output is correct
10 Correct 483 ms 17932 KB Output is correct
11 Correct 3 ms 4932 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 61 ms 123980 KB Output is correct
3 Correct 60 ms 124704 KB Output is correct
4 Correct 3 ms 4932 KB Output is correct
5 Correct 3 ms 2644 KB Output is correct
6 Correct 59 ms 123872 KB Output is correct
7 Correct 4 ms 7364 KB Output is correct
8 Correct 8 ms 16668 KB Output is correct
9 Correct 57 ms 119160 KB Output is correct
10 Correct 47 ms 77736 KB Output is correct
11 Correct 18 ms 26068 KB Output is correct
12 Runtime error 138 ms 256000 KB Execution killed with signal 9
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 81 ms 123972 KB Output is correct
3 Correct 75 ms 124760 KB Output is correct
4 Correct 4 ms 4932 KB Output is correct
5 Correct 2 ms 2644 KB Output is correct
6 Correct 59 ms 123964 KB Output is correct
7 Correct 5 ms 7364 KB Output is correct
8 Correct 9 ms 16708 KB Output is correct
9 Correct 61 ms 119220 KB Output is correct
10 Correct 51 ms 77804 KB Output is correct
11 Correct 15 ms 26084 KB Output is correct
12 Correct 659 ms 25848 KB Output is correct
13 Correct 439 ms 26536 KB Output is correct
14 Correct 458 ms 23220 KB Output is correct
15 Correct 482 ms 22864 KB Output is correct
16 Correct 361 ms 23336 KB Output is correct
17 Correct 473 ms 22972 KB Output is correct
18 Correct 424 ms 22652 KB Output is correct
19 Runtime error 129 ms 256000 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2644 KB Output is correct
2 Correct 60 ms 124136 KB Output is correct
3 Correct 67 ms 124732 KB Output is correct
4 Correct 3 ms 4932 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 61 ms 123964 KB Output is correct
7 Correct 4 ms 7364 KB Output is correct
8 Correct 8 ms 16668 KB Output is correct
9 Correct 54 ms 119156 KB Output is correct
10 Correct 35 ms 77764 KB Output is correct
11 Correct 13 ms 26200 KB Output is correct
12 Correct 556 ms 25792 KB Output is correct
13 Correct 428 ms 26556 KB Output is correct
14 Correct 448 ms 23320 KB Output is correct
15 Correct 525 ms 22904 KB Output is correct
16 Correct 355 ms 23384 KB Output is correct
17 Correct 483 ms 23072 KB Output is correct
18 Correct 480 ms 22652 KB Output is correct
19 Runtime error 128 ms 256000 KB Execution killed with signal 9
20 Halted 0 ms 0 KB -