답안 #1030043

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1030043	2024-07-21T17:19:58 Z	tolbi	게임 (IOI13_game)	C++17	100 / 100	4564 ms	67664 KB

game

#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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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