oj.uz

Submission #805718

# Submission time Handle Problem Language Result Execution time Memory
805718 2023-08-03T21:22:10 Z tolbi Game (IOI13_game) C++17
100 / 100
 2086 ms 87776 KB 
#pragma optimize("Bismillahirrahmanirrahim")
//█▀█─█──█──█▀█─█─█
//█▄█─█──█──█▄█─█■█
//█─█─█▄─█▄─█─█─█─█
//Allahuekber
//ahmet23 orz...
//FatihSultanMehmedHan
//YavuzSultanSelimHan
//AbdulhamidHan
//Sani buyuk Osman Pasa Plevneden cikmam diyor
#define author tolbi
#include <bits/stdc++.h>
using namespace std;
template<typename X, typename Y> ostream& operator<<(ostream& os, pair<X,Y> pr) {return os<<pr.first<<" "<<pr.second;}
template<typename X> ostream& operator<<(ostream& os, vector<X> v){for (auto &it : v) os<<it<<" ";return os;}
template<typename X, size_t Y> ostream& operator<<(ostream& os, array<X,Y> v){for (auto &it : v) os<<it<<" ";return os;}
ostream& operator<<(ostream& os, bool bl){return os<<(int32_t)bl;}
#define endl '\n'
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define cinarr(x) for(auto &it : x) cin>>it;
#define coutarr(x) for(auto &it : x) cout<<it<<" ";cout<<endl;
#define sortarr(x) sort(x.begin(), x.end())
#define sortrarr(x) sort(x.rbegin(), x.rend())
#define rev(x) reverse(x.begin(), x.end())
#define tol(bi) (1ll<<((int)(bi)))
typedef long long ll;
const ll INF = LONG_LONG_MAX;
const ll MOD = 1e9+9;
mt19937 ayahya(chrono::high_resolution_clock().now().time_since_epoch().count());
#include "game.h"

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;
}
const int LIMN=1e9;
const int LIMM=1e9;
struct SegTree{
	struct Node{
		int l, r;
		Node *lnode, *rnode;
		long long val;
		Node(int tl=0, int tr=LIMM):l(tl),r(tr),lnode(nullptr),rnode(nullptr),val(0){}
	};
	Node *root;
	SegTree():root(new Node()){}
	void update(int x, long long val, Node *node=nullptr){
		if (node==nullptr) node = root;
		int l = node->l;
		int r = node->r;
		if (l==r){
			node->val=val;
			return;
		}
		int mid = l+(r-l)/2;
		Node** child;
		bool left = false;
		if (x<=mid) child=&node->lnode,left=true;
		else child=&node->rnode;
		if ((*child)==nullptr){
			(*child)=new Node(x,x);
			(*child)->val=val;
		}
		else if ((*child)->l <= x && (*child)->r >= x){
			update(x, val, (*child));
		}
		else {
			if (x<=mid)r=mid;
			else l=mid+1;
			mid=l+(r-l)/2;			
			while ((x<=mid) == ((*child)->r<=mid)){
				if (x<=mid)r=mid;
				else l=mid+1;
				mid=l+(r-l)/2;
			}
			Node *cur = new Node(l,r);
			if ((*child)->l<x) cur->lnode=(*child);
			else cur->rnode=*child;
			if (left) node->lnode=cur;
			else node->rnode=cur;
			update(x, val, cur);
		}
		long long updval = 0;
		if (node->lnode!=nullptr) updval=gcd2(updval, node->lnode->val);
		if (node->rnode!=nullptr) updval=gcd2(updval, node->rnode->val);
		node->val=updval;
	}
	long long query(int tarl, int tarr, Node *node=nullptr, bool first=true){
		if (first) node=root;
		if (node==nullptr) return 0;
		int l = node->l;
		int r = node->r;
		if (l>=tarl && r<=tarr){
			return node->val;
		}
		if (l>tarr || r<tarl) return 0;
		assert(!first || node->lnode || node->rnode);
		long long lnode = query(tarl, tarr, node->lnode, false);
		long long rnode = query(tarl, tarr, node->rnode, false);
		return gcd2(lnode, rnode);
	}
};
struct SegTree2D{
	struct Node{
		Node *lnode, *rnode;
		SegTree segtree;
		Node():lnode(nullptr),rnode(nullptr),segtree(){}
		Node *crl(){
			if (lnode==nullptr) lnode=new Node();
			return lnode;
		}
		Node* crr(){
			if (rnode==nullptr) rnode=new Node();
			return rnode;
		}
	};
	Node *root;
	SegTree2D():root(new Node()){}
	void update(int x, int y, long long val, int l = 0, int r = LIMN, Node* node=nullptr){
		if (l==0 && r==LIMN) node = root;
		if (l==r){
			node->segtree.update(y,val);
			return;
		}
		if (l>x || r<x) return;
		int mid = l+(r-l)/2;
		if (x<=mid){
			update(x, y, val, l, mid, node->crl());
		}
		else {
			update(x, y, val, mid+1, r, node->crr());
		}
		long long updval = 0;
		if (node->lnode!=nullptr) updval=gcd2(updval, node->lnode->segtree.query(y,y));
		if (node->rnode!=nullptr) updval=gcd2(updval, node->rnode->segtree.query(y,y));
		node->segtree.update(y,updval);
	}
	long long query(int tarl, int tarr, int _l, int _r, int l = 0, int r = LIMN, Node* node=nullptr){
		if (l==0 && r==LIMN) node = root;
		if (node==nullptr) return 0;
		if (l>=tarl && r<=tarr){
			return node->segtree.query(_l, _r);
		}
		if (l>tarr || r<tarl) return 0;
		int mid = l+(r-l)/2;
		long long lnode = query(tarl, tarr, _l, _r, l, mid, node->lnode);
		long long rnode = query(tarl, tarr, _l, _r, mid+1, r, node->rnode);
		return gcd2(lnode, rnode);
	}
};
SegTree2D segtree;
void init(int R, int C) {
    /* ahmet23 really orz!.. */
}
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:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("Bismillahirrahmanirrahim")
      |

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 428 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 212 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 481 ms 36484 KB Output is correct
5 Correct 336 ms 36188 KB Output is correct
6 Correct 534 ms 33920 KB Output is correct
7 Correct 587 ms 33600 KB Output is correct
8 Correct 397 ms 19800 KB Output is correct
9 Correct 575 ms 33624 KB Output is correct
10 Correct 548 ms 33332 KB Output is correct
11 Correct 1 ms 212 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 300 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 320 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 432 KB Output is correct
7 Correct 1 ms 300 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 558 ms 17800 KB Output is correct
13 Correct 891 ms 10940 KB Output is correct
14 Correct 243 ms 5728 KB Output is correct
15 Correct 977 ms 13912 KB Output is correct
16 Correct 265 ms 17916 KB Output is correct
17 Correct 594 ms 14480 KB Output is correct
18 Correct 985 ms 19372 KB Output is correct
19 Correct 870 ms 19516 KB Output is correct
20 Correct 825 ms 19020 KB Output is correct
21 Correct 1 ms 212 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 468 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 300 KB Output is correct
9 Correct 1 ms 424 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 483 ms 36480 KB Output is correct
13 Correct 347 ms 36216 KB Output is correct
14 Correct 569 ms 33964 KB Output is correct
15 Correct 604 ms 33564 KB Output is correct
16 Correct 361 ms 19788 KB Output is correct
17 Correct 576 ms 33764 KB Output is correct
18 Correct 552 ms 33336 KB Output is correct
19 Correct 550 ms 17664 KB Output is correct
20 Correct 870 ms 10880 KB Output is correct
21 Correct 252 ms 5776 KB Output is correct
22 Correct 956 ms 13880 KB Output is correct
23 Correct 261 ms 17976 KB Output is correct
24 Correct 598 ms 14424 KB Output is correct
25 Correct 989 ms 19288 KB Output is correct
26 Correct 869 ms 19472 KB Output is correct
27 Correct 793 ms 18988 KB Output is correct
28 Correct 314 ms 45900 KB Output is correct
29 Correct 835 ms 48188 KB Output is correct
30 Correct 1575 ms 36640 KB Output is correct
31 Correct 1434 ms 29668 KB Output is correct
32 Correct 268 ms 10160 KB Output is correct
33 Correct 363 ms 10756 KB Output is correct
34 Correct 441 ms 41932 KB Output is correct
35 Correct 622 ms 28428 KB Output is correct
36 Correct 1146 ms 46048 KB Output is correct
37 Correct 930 ms 46244 KB Output is correct
38 Correct 963 ms 45672 KB Output is correct
39 Correct 807 ms 37804 KB Output is correct
40 Correct 1 ms 212 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 468 KB Output is correct
3 Correct 1 ms 468 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 500 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 498 ms 36492 KB Output is correct
13 Correct 343 ms 36300 KB Output is correct
14 Correct 524 ms 33868 KB Output is correct
15 Correct 592 ms 33576 KB Output is correct
16 Correct 365 ms 19728 KB Output is correct
17 Correct 567 ms 33648 KB Output is correct
18 Correct 573 ms 33296 KB Output is correct
19 Correct 563 ms 17636 KB Output is correct
20 Correct 905 ms 11060 KB Output is correct
21 Correct 248 ms 5664 KB Output is correct
22 Correct 956 ms 13944 KB Output is correct
23 Correct 263 ms 17892 KB Output is correct
24 Correct 599 ms 14616 KB Output is correct
25 Correct 1020 ms 19388 KB Output is correct
26 Correct 878 ms 19524 KB Output is correct
27 Correct 804 ms 18940 KB Output is correct
28 Correct 319 ms 45976 KB Output is correct
29 Correct 884 ms 48192 KB Output is correct
30 Correct 1586 ms 36708 KB Output is correct
31 Correct 1428 ms 29672 KB Output is correct
32 Correct 270 ms 10184 KB Output is correct
33 Correct 368 ms 10688 KB Output is correct
34 Correct 437 ms 41820 KB Output is correct
35 Correct 650 ms 28376 KB Output is correct
36 Correct 1199 ms 46188 KB Output is correct
37 Correct 902 ms 46144 KB Output is correct
38 Correct 878 ms 45780 KB Output is correct
39 Correct 431 ms 86764 KB Output is correct
40 Correct 1431 ms 87776 KB Output is correct
41 Correct 2086 ms 70324 KB Output is correct
42 Correct 1914 ms 54792 KB Output is correct
43 Correct 642 ms 82464 KB Output is correct
44 Correct 321 ms 10724 KB Output is correct
45 Correct 774 ms 37784 KB Output is correct
46 Correct 1694 ms 86668 KB Output is correct
47 Correct 1723 ms 86740 KB Output is correct
48 Correct 1619 ms 86176 KB Output is correct
49 Correct 1 ms 212 KB Output is correct