Submission #399554

#	Time	Username	Problem	Language	Result	Execution time	Memory
399554		cfalas	Game (IOI13_game)	C++14	63 / 100	3120 ms	256004 KiB

game

#include "game.h"
#include<bits/stdc++.h>
using namespace std;
#define mp make_pair
#define INF 10000000
#define MOD 1000000007
#define MID ((l+r)/2)
#define HASHMOD 2305843009213693951
#define ll long long
#define ull unsigned long long
#define F first
#define S second
typedef pair<ll, ll> ii;
typedef pair<ii, int> iii;
typedef vector<ll> vi;
typedef vector<ii> vii;
typedef map<int, int> mii;

#define EPS 1e-6
#define FOR(i,n) for(int i=0;i<((int)(n));i++)
#define FORi(i,a,b) for(int i=((int)(a));i<((int)(b));i++)
#define FOA(v, a) for(auto v : a)

int t, n;
vi a, b;

static int M;
//static map<int, map<ii, int> > mapper;

long long gcd(long long X, long long Y) {
	//return X + Y;
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}


template<typename Q>
struct seg_tree_2d{

	template<typename T>
	struct seg_tree{
		struct node{
			T val;
			node* left=nullptr;
			node* right=nullptr;
			node() {val=0;}
			node(T v) {val=v;}
		};
		node* root=nullptr;
		T RAND_VALUE=0;
		seg_tree(){root = new node();}

		unordered_map<int, T> leaves;
		inline void merge(node *par){
			par->val = gcd(par->left->val , par->right->val);
		}

		inline void update_node(node* ind, T val, int l, int r){
			//cout<<"Updating "<<l<<" "<<r<<endl;
			leaves[l] = val;
			if(val==0) leaves.erase(l);
			ind->val = val;
		}

		inline void create_children(node* ind){
			if(ind->left==nullptr) ind->left= new node();
			if(ind->right==nullptr) ind->right = new node();
		}

		void print(node* ind, int l=0, int r=M-1){
			cout<<"("<<l<<" "<<r<<": "<<ind->val<<") ";
			if(ind->left!=nullptr) print(ind->left, l, MID);
			if(ind->right!=nullptr) print(ind->right, MID+1, r);
		}

		void build(node* ind, vector<T>& arr, int l=0, int r=M-1){
			if(l==r) ind->val = node(arr[l]);
			else{
				create_children(ind);
				build(ind->left, arr,l,MID);
				build(ind->right, arr,MID+1,r);

				merge(ind);
			}
		}

		void update(node* ind, int x, T val, int l=0, int r=M-1){
			if(x==l && r==x) update_node(ind, val,l,r);
			else if(x<l || r<x) return;
			else{
				create_children(ind);
				update(ind->left, x,val,l,MID);
				update(ind->right, x,val,MID+1,r);
				merge(ind);
			}
		}

		T query(node* ind, int rl, int rr, int l=0, int r=M-1){
			if(rl<=l && r<=rr) return ind->val;
			else if(rl>r || l>rr) return RAND_VALUE;
			else{
				create_children(ind);
				return  gcd(query(ind->left, rl, rr, l, MID) , query(ind->right, rl,rr,MID+1,r));
			}
		}


	};
	struct node{
		seg_tree<Q>* val = new seg_tree<Q>;
		int left=-1;
		int right=-1;
		node() {left=-1, right=-1;}
	};
	vector<node> seg2d;
	static inline int N;
	Q RAND_VALUE_2d=0;
	seg_tree_2d(int n){N=n, seg2d.assign(1, node());}

	inline void merge(node &par, node &a, node &b, int ind){
		/*
		cout<<"Merging "<<seg2d[ind].left<<" "<<seg2d[ind].right<<endl;
		cout<<&a<<" "<<&b<<" "<<&par<<endl;
		a.val->print();
		cout<<endl;
		b.val->print();
		cout<<endl;
		par.val->print();
		cout<<endl;
		cout<<"LEAVES A: ";
		FOA(v, a.val->leaves) cout<<"("<<v.F<<" "<<v.S<<") ";
		cout<<endl;
		cout<<"LEAVES B: ";
		FOA(v, b.val->leaves) cout<<"("<<v.F<<" "<<v.S<<") ";
		cout<<endl;
		*/
		FOA(v,a.val->leaves){
			Q val = v.S;
			if(b.val->leaves[v.F]) val = gcd(val, b.val->leaves[v.F]);
			if(par.val->leaves[v.F]!=val) par.val->update(par.val->root, v.F, val);
		}
		FOA(v,b.val->leaves){
			Q val = v.S;
			if(a.val->leaves[v.F]) val = gcd(val, a.val->leaves[v.F]);
			if(par.val->leaves[v.F]!=val) par.val->update(par.val->root, v.F, val);
		}
		/*
		cout<<"LEAVES combo: ";
		FOA(v, par.val->leaves) cout<<"("<<v.F<<" "<<v.S<<") ";
		cout<<endl;
		*/
	}

	void print(int l=0, int r=N-1, int ind=0){
		cout<<"L R "<<l<<" "<<r<<" "<<ind<<endl;
		//seg2d[ind].val->print();
		cout<<endl;
		if(seg2d[ind].left!=-1) print(l, MID, seg2d[ind].left);
		if(seg2d[ind].right!=-1) print(MID+1, r, seg2d[ind].right);
	}

	inline void create_children(int ind){
		if(seg2d[ind].left==-1){
			seg2d[ind].left=seg2d.size();
			seg2d.push_back(node());
		}
		if(seg2d[ind].right==-1){
			seg2d[ind].right=seg2d.size();
			seg2d.push_back(node());
		}
	}

	/*
	void build(vector<vector<Q> >& arr, int l=0, int r=N-1, int ind=0){
		if(l==r){
			seg2d[ind].val.build(arr[l]);
		}
		else{
			create_children(ind);
			build(arr,l,MID,seg2d[ind].left);
			build(arr,MID+1,r,seg2d[ind].right);

			merge(seg2d[ind], seg2d[seg2d[ind].left], seg2d[seg2d[ind].right], ind);
		}
	}
	*/

	void update(int y, int x, Q val, int l=0, int r=N-1, int ind=0){
		if(y==l && y==r) seg2d[ind].val->update(seg2d[ind].val->root, x, val);
		else if(y<l || r<y) return;
		else{
			create_children(ind);
			update(y,x,val,l,MID,seg2d[ind].left);
			update(y,x,val,MID+1,r,seg2d[ind].right);
			Q g = seg2d[seg2d[ind].left].val->query(seg2d[seg2d[ind].left].val->root, x, x);
			g = gcd(g, seg2d[seg2d[ind].right].val->query(seg2d[seg2d[ind].right].val->root, x, x));
			if(seg2d[ind].val->query(seg2d[ind].val->root, x, x)!= g){
				seg2d[ind].val->update(seg2d[ind].val->root, x, g);
			}
			//merge(seg2d[ind], seg2d[seg2d[ind].left], seg2d[seg2d[ind].right], ind);
		}
	}

	Q query(int rl, int rr, int xl, int xr, int l=0, int r=N-1, int ind=0){
		if(rl<=l && r<=rr) return seg2d[ind].val->query(seg2d[ind].val->root, xl, xr);
		else if(rl>r || l>rr) return RAND_VALUE_2d;
		else{
			create_children(ind);
			return gcd(query(rl, rr, xl, xr, l, MID, seg2d[ind].left), query(rl,rr,xl, xr, MID+1,r,seg2d[ind].right));
		}
	}

};

seg_tree_2d<ll> seg(n);

void init(int R, int C) {
	M = R;
	seg.N = C;
}

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

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

Compilation message (stderr)

game.cpp:121:9: warning: inline variables are only available with '-std=c++17' or '-std=gnu++17'
  121 |  static inline int N;
      |         ^~~~~~

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