oj.uz

Submission #1030043

# Submission time Handle Problem Language Result Execution time Memory
1030043 2024-07-21T17:19:58 Z tolbi Game (IOI13_game) C++17
100 / 100
 4564 ms 67664 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
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;
}
mt19937_64 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
struct Treap{
	struct Node{
		Node *lnode, *rnode;
		ll val, gg, h;
		int pos;
		Node(int pos, ll x):val(x),gg(x),h(ayahya()),pos(pos),lnode(nullptr),rnode(nullptr){}
	} *root;
	Treap():root(nullptr){}
	void upd(Node* nd){
		nd->gg=nd->val;
		if (nd->lnode) nd->gg=gcd2(nd->lnode->gg,nd->gg);
		if (nd->rnode) nd->gg=gcd2(nd->rnode->gg,nd->gg);
	}
	Node* merge(Node* a, Node* b){
		if (!a || !b) return (a?a:b);
		if (a->h > b->h) return a->rnode = merge(a->rnode,b),upd(a),a;
		return b->lnode = merge(a,b->lnode),upd(b),b;
	}
	pair<Node*, Node*> split(Node* node, int x){
		if (!node) return {nullptr,nullptr};
		if (node->pos>=x){
			pair<Node*, Node*> spl = split(node->lnode,x);
			node->lnode=spl.second;
			upd(node);
			return {spl.first,node};
		}
		pair<Node*, Node*> spl = split(node->rnode,x);
		node->rnode=spl.first;
		upd(node);
		return {node,spl.second};
	}
	void update(int x, ll val){
		if (root==nullptr){
			return root = new Node(x,val), void(23);
		}
		Node* nd = root;
		while (nd){
			if (nd->pos==x) break;
			if (nd->pos>x) nd=nd->lnode;
			else nd=nd->rnode;
		}
		if (nd==nullptr){
			Node* nnode = new Node(x,val);
			pair<Node*, Node*> spl = split(root,x);
			root=merge(spl.first,nnode);
			root=merge(root,spl.second);
		}
		else {
			vector<Node*> backtrack;
			nd->val=val;
			upd(nd);
			nd = root;
			while (nd->pos!=x){
				backtrack.push_back(nd);
				if (nd->pos>x) nd=nd->lnode;
				else nd=nd->rnode;
			}
			while (backtrack.size()){
				upd(backtrack.back());
				backtrack.pop_back();
			}
		}
	}
	ll query(int l, int r){
		pair<Node*, Node*> spl = split(root, l);
		pair<Node*, Node*> spl2 = split(spl.second, r+1);
		ll ret = 0;
		if (spl2.first) ret = spl2.first->gg;
		root = merge(spl2.first,spl2.second);
		root = merge(spl.first,root);
		return ret;
	}
};
constexpr int MAXN = 1000000000;
struct SegTree{
	struct Node{
		Node *lnode, *rnode;
		Treap tr;
		Node():lnode(nullptr),rnode(nullptr){}
	} *root;
	SegTree():root(new Node){}
	void update(int x, int y, ll val, int l = 0, int r = MAXN, Node* nd = nullptr){
		if (l==0 && r==MAXN) nd=root;
		if (l==r){
			return nd->tr.update(y,val);
		}
		int mid = l+(r-l)/2;
		if (mid>=x){
			if (nd->lnode==nullptr) nd->lnode=new Node;
			update(x,y,val,l,mid,nd->lnode);
		}
		else {
			if (nd->rnode==nullptr) nd->rnode=new Node;
			update(x,y,val,mid+1,r,nd->rnode);
		}
		ll ret = 0;
		if (nd->lnode) ret=nd->lnode->tr.query(y,y);
		if (nd->rnode) ret=gcd2(nd->rnode->tr.query(y,y),ret);
		nd->tr.update(y,ret);
	}
	ll query(int tl, int tr, int a, int b, int l = 0, int r = MAXN, Node* node = nullptr){
		if (l==0 && r==MAXN) node=root;
		if (l>=tl && r<=tr) return node->tr.query(a,b);
		if (l>tr || r<tl) return 0;
		int mid = l+(r-l)/2;
		ll ret = 0;
		if (node->lnode && mid>=tl) ret=gcd2(ret,query(tl,tr,a,b,l,mid,node->lnode));
		if (node->rnode && mid<tr) ret=gcd2(ret,query(tl,tr,a,b,mid+1,r,node->rnode));
		return ret;
	}
} segtree;
void init(int R, int C) {
	//23 severim
}

void update(int P, int Q, long long K) {
	segtree.update(P,Q,K);
}

long long calculate(int P, int Q, int U, int V) {
	return segtree.query(P,U,Q,V);
}

Compilation message

game.cpp: In constructor 'Treap::Node::Node(int, ll)':
game.cpp:19:7: warning: 'Treap::Node::pos' will be initialized after [-Wreorder]
   19 |   int pos;
      |       ^~~
game.cpp:17:9: warning:   'Treap::Node* Treap::Node::lnode' [-Wreorder]
   17 |   Node *lnode, *rnode;
      |         ^~~~~
game.cpp:20:3: warning:   when initialized here [-Wreorder]
   20 |   Node(int pos, ll x):val(x),gg(x),h(ayahya()),pos(pos),lnode(nullptr),rnode(nullptr){}
      |   ^~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 1076 ms 27268 KB Output is correct
5 Correct 722 ms 26964 KB Output is correct
6 Correct 1940 ms 24704 KB Output is correct
7 Correct 2009 ms 24444 KB Output is correct
8 Correct 1183 ms 15160 KB Output is correct
9 Correct 1946 ms 24476 KB Output is correct
10 Correct 1704 ms 24100 KB Output is correct
11 Correct 0 ms 344 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 5 ms 348 KB Output is correct
3 Correct 3 ms 348 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 4 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 3 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 2 ms 604 KB Output is correct
12 Correct 1038 ms 14648 KB Output is correct
13 Correct 1673 ms 9040 KB Output is correct
14 Correct 434 ms 5712 KB Output is correct
15 Correct 1765 ms 11252 KB Output is correct
16 Correct 694 ms 13840 KB Output is correct
17 Correct 1823 ms 11824 KB Output is correct
18 Correct 3177 ms 15200 KB Output is correct
19 Correct 2717 ms 15328 KB Output is correct
20 Correct 2427 ms 15092 KB Output is correct
21 Correct 1 ms 348 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 4 ms 348 KB Output is correct
3 Correct 3 ms 344 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 440 KB Output is correct
6 Correct 4 ms 344 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 3 ms 656 KB Output is correct
10 Correct 1 ms 472 KB Output is correct
11 Correct 2 ms 348 KB Output is correct
12 Correct 1010 ms 27216 KB Output is correct
13 Correct 642 ms 27028 KB Output is correct
14 Correct 1647 ms 24576 KB Output is correct
15 Correct 1797 ms 24324 KB Output is correct
16 Correct 1018 ms 15144 KB Output is correct
17 Correct 1764 ms 24432 KB Output is correct
18 Correct 1431 ms 24088 KB Output is correct
19 Correct 811 ms 14676 KB Output is correct
20 Correct 1403 ms 9068 KB Output is correct
21 Correct 311 ms 5656 KB Output is correct
22 Correct 1595 ms 11264 KB Output is correct
23 Correct 720 ms 13912 KB Output is correct
24 Correct 1578 ms 11980 KB Output is correct
25 Correct 2678 ms 15272 KB Output is correct
26 Correct 2464 ms 15304 KB Output is correct
27 Correct 2278 ms 14652 KB Output is correct
28 Correct 724 ms 36320 KB Output is correct
29 Correct 1360 ms 39084 KB Output is correct
30 Correct 2550 ms 28328 KB Output is correct
31 Correct 1998 ms 23364 KB Output is correct
32 Correct 367 ms 10220 KB Output is correct
33 Correct 521 ms 10452 KB Output is correct
34 Correct 950 ms 32736 KB Output is correct
35 Correct 1674 ms 23892 KB Output is correct
36 Correct 3390 ms 36832 KB Output is correct
37 Correct 2673 ms 37140 KB Output is correct
38 Correct 2576 ms 36368 KB Output is correct
39 Correct 2308 ms 30964 KB Output is correct
40 Correct 1 ms 348 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 4 ms 596 KB Output is correct
3 Correct 4 ms 344 KB Output is correct
4 Correct 0 ms 440 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 4 ms 344 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 3 ms 344 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 2 ms 348 KB Output is correct
12 Correct 1195 ms 27152 KB Output is correct
13 Correct 711 ms 27008 KB Output is correct
14 Correct 1823 ms 24600 KB Output is correct
15 Correct 1972 ms 24452 KB Output is correct
16 Correct 1100 ms 15220 KB Output is correct
17 Correct 1944 ms 24448 KB Output is correct
18 Correct 1682 ms 24080 KB Output is correct
19 Correct 1090 ms 14660 KB Output is correct
20 Correct 1772 ms 8984 KB Output is correct
21 Correct 432 ms 5716 KB Output is correct
22 Correct 1750 ms 11280 KB Output is correct
23 Correct 773 ms 13700 KB Output is correct
24 Correct 1721 ms 12148 KB Output is correct
25 Correct 2785 ms 15112 KB Output is correct
26 Correct 2546 ms 15444 KB Output is correct
27 Correct 2295 ms 14676 KB Output is correct
28 Correct 705 ms 36408 KB Output is correct
29 Correct 1239 ms 38980 KB Output is correct
30 Correct 2145 ms 28232 KB Output is correct
31 Correct 1920 ms 23388 KB Output is correct
32 Correct 361 ms 10220 KB Output is correct
33 Correct 474 ms 10568 KB Output is correct
34 Correct 912 ms 32760 KB Output is correct
35 Correct 1787 ms 23776 KB Output is correct
36 Correct 3494 ms 36804 KB Output is correct
37 Correct 2817 ms 37024 KB Output is correct
38 Correct 2554 ms 36332 KB Output is correct
39 Correct 1012 ms 65620 KB Output is correct
40 Correct 2288 ms 67664 KB Output is correct
41 Correct 3598 ms 52248 KB Output is correct
42 Correct 3253 ms 41176 KB Output is correct
43 Correct 1798 ms 62368 KB Output is correct
44 Correct 704 ms 10588 KB Output is correct
45 Correct 2325 ms 30828 KB Output is correct
46 Correct 4550 ms 66468 KB Output is correct
47 Correct 4564 ms 66364 KB Output is correct
48 Correct 4510 ms 65932 KB Output is correct
49 Correct 1 ms 348 KB Output is correct