oj.uz

Submission #1025724

# Submission time Handle Problem Language Result Execution time Memory
1025724 2024-07-17T09:15:28 Z dozer Game (IOI13_game) C++14
63 / 100
 1218 ms 256000 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


const int M = 1e9;

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

	void pull_x(){
		ll lft = 0, rgt = 0;
		if (XL != NULL) lft = XL->valy;
		if (XR != NULL) rgt = XR->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;
		R = M, C = M;
	}

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

		int mid = (l + r) / 2;

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

		else{
			if (node->YR == NULL){
				node->YR = new Node();
			}
			if (node-> XL != NULL) node->YR->XL = node->XL->YR;
			if (node->XR != NULL) node->YR->XR = node->XR->YR;
			update_y(node->YR, mid + 1, r, a, b, 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;
		
		if (l != r){
			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);
			}
		}

		update_y(node, 1, C, l, r, 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) {
			ll val = query_y(node, 1, C, c, d);
			return val;
		}
		ll 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);
}


/*
#define fail(s, x...) do { \
		fprintf(stderr, s "\n", ## x); \
		exit(1); \
	} while(0)

#define MAX_SIZE 1000000000
#define MAX_N 272000

int main() {
	int R, C, N;
    int P, Q, U, V;
    long long K;
    int i, type;
	int res;

	freopen("output.txt", "w", stdout);

	FILE *f = fopen("input.txt", "r");
	if (!f)
		fail("Failed to open input file.");

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

    init(R, C);

	for (i = 0; i < N; i++) {
        res = fscanf(f, "%d", &type);
        if (type == 1) {
		    res = fscanf(f, "%d%d%lld", &P, &Q, &K);
            update(P, Q, K);
        } else if (type == 2) {
		    res = fscanf(f, "%d%d%d%d", &P, &Q, &U, &V);
            printf("%lld\n", calculate(P, Q, U, V));
        } else
			fail("Invalid action type in input file.");
	}
	fclose(f);

	return 0;
}
*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 656 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 0 ms 600 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 562 ms 77724 KB Output is correct
5 Correct 390 ms 77136 KB Output is correct
6 Correct 554 ms 75164 KB Output is correct
7 Correct 576 ms 74832 KB Output is correct
8 Correct 376 ms 46420 KB Output is correct
9 Correct 572 ms 75344 KB Output is correct
10 Correct 534 ms 74740 KB Output is correct
11 Correct 1 ms 348 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 2 ms 856 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 864 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 436 KB Output is correct
9 Correct 2 ms 860 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 773 ms 29468 KB Output is correct
13 Correct 930 ms 16732 KB Output is correct
14 Correct 299 ms 6024 KB Output is correct
15 Correct 1047 ms 23872 KB Output is correct
16 Correct 318 ms 38500 KB Output is correct
17 Correct 808 ms 27876 KB Output is correct
18 Correct 1215 ms 39828 KB Output is correct
19 Correct 1086 ms 39864 KB Output is correct
20 Correct 1036 ms 39184 KB Output is correct
21 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 436 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 2 ms 856 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 532 ms 77652 KB Output is correct
13 Correct 409 ms 77000 KB Output is correct
14 Correct 555 ms 75144 KB Output is correct
15 Correct 570 ms 74832 KB Output is correct
16 Correct 380 ms 46420 KB Output is correct
17 Correct 565 ms 75340 KB Output is correct
18 Correct 533 ms 74836 KB Output is correct
19 Correct 754 ms 29596 KB Output is correct
20 Correct 923 ms 16764 KB Output is correct
21 Correct 308 ms 5976 KB Output is correct
22 Correct 1018 ms 23892 KB Output is correct
23 Correct 317 ms 38480 KB Output is correct
24 Correct 801 ms 27856 KB Output is correct
25 Correct 1218 ms 39760 KB Output is correct
26 Correct 1105 ms 40020 KB Output is correct
27 Correct 1034 ms 39252 KB Output is correct
28 Runtime error 406 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 2 ms 856 KB Output is correct
3 Correct 1 ms 944 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 2 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 944 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 604 KB Output is correct
12 Correct 504 ms 77700 KB Output is correct
13 Correct 404 ms 77136 KB Output is correct
14 Correct 583 ms 75188 KB Output is correct
15 Correct 599 ms 75100 KB Output is correct
16 Correct 386 ms 46424 KB Output is correct
17 Correct 565 ms 75344 KB Output is correct
18 Correct 500 ms 74744 KB Output is correct
19 Correct 724 ms 29524 KB Output is correct
20 Correct 887 ms 16720 KB Output is correct
21 Correct 295 ms 6004 KB Output is correct
22 Correct 1037 ms 23796 KB Output is correct
23 Correct 319 ms 38740 KB Output is correct
24 Correct 753 ms 28068 KB Output is correct
25 Correct 1144 ms 39648 KB Output is correct
26 Correct 1032 ms 40016 KB Output is correct
27 Correct 1022 ms 39316 KB Output is correct
28 Runtime error 380 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -