Submission #805718

#	Time	Username	Problem	Language	Result	Execution time	Memory
805718		tolbi	Game (IOI13_game)	C++17	100 / 100	2086 ms	87776 KiB

game

#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 (stderr)

game.cpp:1: warning: ignoring '#pragma optimize ' [-Wunknown-pragmas]
    1 | #pragma optimize("Bismillahirrahmanirrahim")
      |

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 17 / 17
• Subtask 5: 20 / 20