Submission #781159

#	Time	Username	Problem	Language	Result	Execution time	Memory
781159		tolbi	Game (IOI13_game)	C++17	0 / 100	1 ms	212 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;}
#define endl '\n'
#define deci(x) int x;cin>>x;
#define decstr(x) string x;cin>>x;
#define vint(x) vector<int> x
#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<<((long long)(bi)))
#define coutarr(x) for (auto &it : x) cout<<it<<endl;
typedef long long ll;
const ll INF = LONG_LONG_MAX;
const int MOD = 1e9+7;
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 MINX = 0;
const int MAXX = 1e9+7;
const int MINY = 0;
const int MAXY = 1e9+7;
struct SegTree2D{
	struct SegTree{
		struct Node{
			int lnode, rnode;
			ll val;
			Node():lnode(-1),rnode(-1),val(0ll){}
		};
		vector<Node> segtree;
		inline int dall(int node){
			if (segtree[node].lnode==-1){
				segtree[node].lnode=segtree.size();
				segtree.push_back(Node());
			}
			return segtree[node].lnode;
		}
		inline int dalr(int node){
			if (segtree[node].rnode==-1){
				segtree[node].rnode=segtree.size();
				segtree.push_back(Node());
			}
			return segtree[node].rnode;
		}
		SegTree(){
			lnode=rnode=-1;
			segtree.push_back(Node());
		}
		int lnode, rnode;
		void update(int x, int val, int l = MINY, int r = MAXY, int node = 0){
			if (l==r && l==x){
				segtree[node].val=val;
				return;
			}
			if (l>x || r<x) return;
			int mid = l+(r-l)/2;
			if (x<=mid){
				update(x, val, l, mid, dall(node));
			}
			else {
				update(x, val, mid+1, r, dalr(node));
			}
			ll lnode = 0, rnode = 0;
			if (segtree[node].lnode!=-1) lnode = segtree[segtree[node].lnode].val;
			if (segtree[node].rnode!=-1) rnode = segtree[segtree[node].rnode].val;
			segtree[node].val=gcd2(lnode, rnode);
		}
		ll query(int tarl, int tarr, int l = MINY, int r = MAXY, int node = 0){
			if (node==-1) return 0;
			if (l>=tarl && r<=tarr) return segtree[node].val;
			if (l>tarr || r<tarl) return 0;
			int mid = l+(r-l)/2;
			ll lnode = query(tarl, tarr, l, mid, segtree[node].lnode);
			ll rnode = query(tarl, tarr, mid+1, r, segtree[node].rnode);
			return gcd2(lnode, rnode);
		}
	};
	vector<SegTree> segtree;
	SegTree2D(){segtree.push_back(SegTree());}
	inline int dall(int node){
		if (segtree[node].lnode==-1){
			segtree[node].lnode=segtree.size();
			segtree.push_back(SegTree());
		}
		return segtree[node].lnode;
	}
	inline int dalr(int node){
		if (segtree[node].rnode==-1){
			segtree[node].rnode=segtree.size();
			segtree.push_back(SegTree());
		}
		return segtree[node].rnode;
	}
	ll query(int tarl, int tarr, int x1, int x2, int l = MINX, int r = MAXX, int node = 0){
		if (node==-1) return 0;
		if (l>=tarl && r<=tarr) return segtree[node].query(x1,x2);
		if (l>tarr || r<tarl) return 0;
		int mid = l+(r-l)/2;
		ll lnode = query(tarl, tarr, x1, x2, l, mid, segtree[node].lnode);
		ll rnode = query(tarl, tarr, x1, x2, mid+1, r, segtree[node].rnode);
		return gcd2(lnode, rnode);
	}
	void update(int x, int y, ll val, int l = MINX, int r = MAXX, int node = 0){
		if (l==x && r==x){
			segtree[node].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, dall(node));
		else update(x, y, val, mid+1, r, dalr(node));

		int left = segtree[node].lnode, right = segtree[node].rnode;
		int pt = 0, ptl = 0, ptr = 0;
		if (left==-1) ptl = -1;
		if (right==-1) ptr = -1;
		l=MINY, r=MAXY;
		while (true){
			ll sag = 0, sol = 0;
			if (ptl!=-1) sol=segtree[left].segtree[ptl].val;
			if (ptr!=-1) sag=segtree[right].segtree[ptr].val;
			segtree[node].segtree[pt].val=gcd2(sol,sag);
			if (l==r) break;
			int mid = l+(r-l)/2;
			if (y<=mid){
				if (ptl!=-1) ptl=segtree[left].segtree[ptl].lnode;
				if (ptr!=-1) ptr=segtree[right].segtree[ptr].lnode;
				pt=segtree[node].dall(pt);
				r=mid;
			}
			else {
				if (ptl!=-1) ptl=segtree[left].segtree[ptl].rnode;
				if (ptr!=-1) ptr=segtree[right].segtree[ptr].rnode;
				pt=segtree[node].dalr(pt);
				l=mid+1;
			}
		}
	}
};
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: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20