oj.uz

Submission #1079949

# Submission time Handle Problem Language Result Execution time Memory
1079949 2024-08-29T04:50:45 Z dozer Game (IOI13_game) C++14
100 / 100
 4831 ms 79040 KB 
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
#define sp " "
#define endl "\n";
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<ll, ll>
#define st first
#define nd second
#define ll long long

const int modulo = 1e9 + 7;


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 Treap{
	struct Node{
		ll h;
		pii b;
		Node *l, *r;
		ll val;
		ll gcdd;

		Node(pii ind, ll v){
			val = v;
			gcdd = v;
			b = ind;
			h = rand();
			l = r = NULL;
		};

		void pull(){
			gcdd = val;
			if (l != NULL) gcdd = gcd2(gcdd, l->gcdd);
			if (r != NULL) gcdd = gcd2(gcdd, r->gcdd);
		}
	};

	typedef Node* pnode;

	pnode root;

	Treap(){
		root = NULL;
	}

	void split(pnode node, pnode &L, pnode &R, pii val){
		if (node == NULL) return;
		if (node->b <= val){
			L = node;
			pnode tmp = NULL;
			split(node->r, tmp, R, val);
			L->r = tmp;
		}
		else{
			R = node;
			pnode tmp = NULL;
			split(node->l, L, tmp, val);
			R->l = tmp;
		}
		if (L != NULL) L->pull();
		if (R != NULL) R->pull();
	}

	void merge(pnode L, pnode R, pnode &res){
		if (L == NULL){
			res = R;
			return;
		}
		if (R == NULL){
			res = L;
			return;
		}
		if (L->h > R->h){
			pnode tmp = NULL;;
			merge(L->r, R, tmp);
			L->r = tmp;
			res = L;
		}
		else{
			pnode tmp = NULL;
			merge(L, R->l, tmp);
			R->l = tmp;
			res = R;
		}
		if (res != NULL) res->pull();
	}

	ll query(ll l, ll r){
		pnode a = NULL, b = NULL, c = NULL, d = NULL;
		split(root, a, b, {l - 1, modulo});
		split(b, c, d, {r, modulo});
		ll ans = 0;
		if (c != NULL) ans = c->gcdd;
		pnode tmp;
		merge(a, c, tmp);
		pnode tmp2;
		merge(tmp, d, root);
		return ans;
	}

	void update(pii ind, ll val){
		pnode a = NULL, b = NULL, c = NULL, d = NULL;
		split(root, a, b, {ind.st, ind.nd - 1});
		split(b, c, d, ind);
		if (c == NULL) c = new Node(ind, val);
		c->val = val;
		c->gcdd = val;
		pnode tmp = NULL;
		merge(a, c, tmp);
		merge(tmp, d, root);
	}
};


struct SegTree{
	struct Node{
		Node *l, *r;
		Treap *t;
		Node(){
			t = new Treap();
			l = r = NULL;
		}
	};


	typedef Node* pnode;
	ll r;

	pnode root;
	SegTree(){
		root = new Node();
	}

	SegTree(ll R){
		root = new Node();
		r = R;
		srand(time(NULL));
	}

	void update(pnode node, ll l, ll r, ll sx, ll sy, ll val){
		node->t->update({sy, sx}, val);
		if (l == r) return;
		ll mid = (l + r) / 2;
		if (sx <= mid){
			if (node->l == NULL) node->l = new Node();
			update(node->l, l, mid, sx, sy, val);
		}
		else{
			if (node->r == NULL) node ->r = new Node();
			update(node->r, mid + 1, r, sx, sy, val);
		}
	}

	ll query(pnode node, ll l, ll r, ll a, ll b, ll c, ll d){
		if (l > b || r < a) return 0;
		if (l >= a && r <= b) {
			ll val = node->t->query(c, d);
			return val;
		}
		ll mid = (l + r) / 2;
		ll ans = 0;
		if (a <= mid && node->l != NULL){
			ans = gcd2(ans, query(node->l, l, mid, a, b, c, d));
		}
		if (b > mid && node->r != NULL){
			ans = gcd2(ans, query(node->r, mid + 1, r, a, b, c, d));
		}
		return ans;
	}

	void update_util(ll sx, ll sy, ll val){
		update(root, 1, r, sx, sy, val);
	}

	ll query_util(ll a, ll b, ll c, ll d){
		return query(root, 1, r, a, b, c, d);
	}
};

ll r, c;
SegTree *t;

void init(int R, int C) {
    t = new SegTree(R);
    r = R, c = C;
}
 
void update(int P, int Q, long long K) {
    t->update_util(P + 1, Q + 1, K);
}
 
long long calculate(int P, int Q, int U, int V) {
    P++, Q++, U++, V++;
    return t->query_util(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;
 
 
	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);
           	printf("%lld\n", calculate(P, Q, U, V));
        } else{
        	printf("%d\n", type);
			fail("Invalid action type in input file.");
        }
	}
 	cerr<<"time taken : "<<(float)clock() / CLOCKS_PER_SEC<<" seconds\n";
	return 0;
}
*/

Compilation message

game.cpp: In member function 'long long int Treap::query(long long int, long long int)':
game.cpp:108:9: warning: unused variable 'tmp2' [-Wunused-variable]
  108 |   pnode tmp2;
      |         ^~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 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 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 364 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 564 ms 11540 KB Output is correct
5 Correct 237 ms 11420 KB Output is correct
6 Correct 979 ms 8884 KB Output is correct
7 Correct 1206 ms 8396 KB Output is correct
8 Correct 770 ms 7572 KB Output is correct
9 Correct 1093 ms 8544 KB Output is correct
10 Correct 955 ms 8156 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 436 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 416 KB Output is correct
8 Correct 0 ms 344 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 925 ms 15488 KB Output is correct
13 Correct 1952 ms 10104 KB Output is correct
14 Correct 368 ms 5780 KB Output is correct
15 Correct 2111 ms 11212 KB Output is correct
16 Correct 264 ms 12880 KB Output is correct
17 Correct 1707 ms 10184 KB Output is correct
18 Correct 2892 ms 14512 KB Output is correct
19 Correct 2462 ms 14420 KB Output is correct
20 Correct 2496 ms 13908 KB Output is correct
21 Correct 0 ms 600 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 348 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 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 589 ms 11568 KB Output is correct
13 Correct 228 ms 11348 KB Output is correct
14 Correct 1002 ms 8784 KB Output is correct
15 Correct 1200 ms 8532 KB Output is correct
16 Correct 751 ms 7512 KB Output is correct
17 Correct 1096 ms 8528 KB Output is correct
18 Correct 988 ms 8276 KB Output is correct
19 Correct 958 ms 15428 KB Output is correct
20 Correct 2021 ms 10048 KB Output is correct
21 Correct 372 ms 5712 KB Output is correct
22 Correct 2142 ms 11052 KB Output is correct
23 Correct 220 ms 13092 KB Output is correct
24 Correct 1675 ms 10320 KB Output is correct
25 Correct 2972 ms 14452 KB Output is correct
26 Correct 2462 ms 14620 KB Output is correct
27 Correct 2501 ms 13892 KB Output is correct
28 Correct 686 ms 41808 KB Output is correct
29 Correct 1409 ms 44624 KB Output is correct
30 Correct 3014 ms 33180 KB Output is correct
31 Correct 2634 ms 27092 KB Output is correct
32 Correct 589 ms 10832 KB Output is correct
33 Correct 896 ms 11484 KB Output is correct
34 Correct 286 ms 38228 KB Output is correct
35 Correct 1923 ms 26724 KB Output is correct
36 Correct 3437 ms 42324 KB Output is correct
37 Correct 2777 ms 42712 KB Output is correct
38 Correct 2861 ms 42068 KB Output is correct
39 Correct 2395 ms 35156 KB Output is correct
40 Correct 0 ms 344 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 1 ms 436 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 344 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 592 ms 11600 KB Output is correct
13 Correct 242 ms 11348 KB Output is correct
14 Correct 980 ms 8860 KB Output is correct
15 Correct 1125 ms 8532 KB Output is correct
16 Correct 752 ms 7508 KB Output is correct
17 Correct 1155 ms 8532 KB Output is correct
18 Correct 985 ms 8520 KB Output is correct
19 Correct 973 ms 15700 KB Output is correct
20 Correct 2008 ms 9900 KB Output is correct
21 Correct 372 ms 5716 KB Output is correct
22 Correct 2165 ms 11228 KB Output is correct
23 Correct 278 ms 12884 KB Output is correct
24 Correct 1709 ms 10216 KB Output is correct
25 Correct 2931 ms 14308 KB Output is correct
26 Correct 2460 ms 14420 KB Output is correct
27 Correct 2512 ms 13896 KB Output is correct
28 Correct 744 ms 41916 KB Output is correct
29 Correct 1444 ms 44472 KB Output is correct
30 Correct 3076 ms 33404 KB Output is correct
31 Correct 2516 ms 27052 KB Output is correct
32 Correct 600 ms 10852 KB Output is correct
33 Correct 820 ms 11380 KB Output is correct
34 Correct 315 ms 38328 KB Output is correct
35 Correct 1893 ms 26748 KB Output is correct
36 Correct 3384 ms 42400 KB Output is correct
37 Correct 2746 ms 42604 KB Output is correct
38 Correct 2878 ms 42068 KB Output is correct
39 Correct 917 ms 77136 KB Output is correct
40 Correct 2291 ms 79040 KB Output is correct
41 Correct 4831 ms 63472 KB Output is correct
42 Correct 4117 ms 49748 KB Output is correct
43 Correct 626 ms 73760 KB Output is correct
44 Correct 1087 ms 12116 KB Output is correct
45 Correct 2335 ms 35276 KB Output is correct
46 Correct 4097 ms 77760 KB Output is correct
47 Correct 4151 ms 77904 KB Output is correct
48 Correct 4067 ms 77480 KB Output is correct
49 Correct 1 ms 344 KB Output is correct