oj.uz

답안 #1025630

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1025630 2024-07-17T08:19:34 Z dozer 게임 (IOI13_game) C++14
0 / 100
 0 ms 348 KB 
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
#define sp " "
#define endl "\n"
#define pb push_back
#define pii pair<int,int>
#define st first
#define nd second
#define fileio() freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define ll long long
#define MAXN 200005


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


struct Node{
	ll valy;
	Node *XL, *XR, *YR, *YL;
	Node(){
		XL = XR = YL = YR = NULL;
		valy = 0;
	}

	void pull_y(){
		ll lft = 0, rgt = 0;
		if (YL != NULL) lft = YL->valy;
		if (YR != NULL) rgt = YR->valy;
		valy = gcd2(lft, rgt);
	}
};


typedef Node* pnode;

struct SegTree{
	pnode root;

	int R, C;

	SegTree(int r, int c){
		root = new Node();
		R = r, C = c;
	}

	void update_y(pnode node, int l, int r, int sl, ll val){
		if (l > sl || r < sl) return;
		if (l == r){
			node->valy = val;
			return;
		}

		int mid = (l + r) / 2;

		if (sl <= mid){
			if (node->YL == NULL){
				node->YL = new Node();
			}
			update_y(node->YL, l, mid, sl, val);
		}

		else{
			if (node->YR == NULL){
				node->YR = new Node();
			}

			update_y(node->YR, mid + 1, r, sl, val);
		}

		node->pull_y();
	}

	void update_x(pnode node, int l, int r, int x, int y, ll val){
		if (l > x || r < x) return;
		update_y(node, 1, C, y, val);
		if (l == r) return;
		int mid = (l + r) / 2;
		if (x <= mid){
			if (node->XL == NULL){
				node->XL = new Node();
			}
			update_x(node->XL, l, mid, x, y, val);
		}

		else{
			if (node->XR == NULL){
				node->XR = new Node();
			}
			update_x(node->XR, mid + 1, r, x, y, val);
		}
	}
	void update(int x, int y, ll val){
		update_x(root, 1, R, x, y, val);
	}


	ll query_y(pnode node, int l, int r, int sl, int sr){
		if (l > sr || r < sl) return 0;
		if (l >= sl && r <= sr) return node->valy;
		ll lft = 0, rgt = 0;
		int mid = (l + r) / 2;
		if (node->YL != NULL && sl <= mid) lft = query_y(node->YL, l, mid, sl, sr);
		if (node->YR != NULL && sr > mid) rgt = query_y(node->YR, mid + 1, r, sl, sr);
		return gcd2(lft, rgt);
	}

	ll query_x(pnode node, int l, int r, int a, int b, int c, int d){
		if (l > b || r < a) return 0;
		if (l >= a && r <= b) {
			int val = query_y(node, 1, C, c, d);
			return val;
		}
		int lft = 0, rgt = 0;
		int mid = (l + r) / 2;
		if (node->XL != NULL && a <= mid){
			lft = query_x(node->XL, l, mid, a, b, c, d);
		}

		if (node->XR != NULL && b > mid){
			rgt = query_x(node->XR, mid + 1, r, a, b, c, d);
		}
		return gcd2(lft, rgt);
	}

	ll query(int a, int b, int c, int d){
		return query_x(root, 1, R, a, b, c, d);
	}
};



SegTree *t;

void init(int R, int C) {
    t = new SegTree(R, C);
}

void update(int P, int Q, long long K) {
    t->update(P + 1, Q + 1, K);
}

long long calculate(int P, int Q, int U, int V) {
    P++, Q++, U++, V++;
    return t->query(P, U, Q, V);
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -