답안 #399554

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
399554	2021-05-06T05:27:24 Z	cfalas	게임 (IOI13_game)	C++14	63 / 100	3120 ms	256004 KB

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

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.0 / 10.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	2 ms	588 KB	Output is correct
3	Correct	2 ms	588 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	460 KB	Output is correct
6	Correct	2 ms	548 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	336 KB	Output is correct
9	Correct	2 ms	548 KB	Output is correct
10	Correct	2 ms	460 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1 ms	204 KB	Output is correct

Subtask #2

27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	208 KB	Output is correct
2	Correct	1 ms	300 KB	Output is correct
3	Correct	1 ms	332 KB	Output is correct
4	Correct	959 ms	47528 KB	Output is correct
5	Correct	701 ms	38720 KB	Output is correct
6	Correct	1467 ms	108308 KB	Output is correct
7	Correct	1491 ms	108196 KB	Output is correct
8	Correct	1258 ms	108808 KB	Output is correct
9	Correct	1442 ms	110380 KB	Output is correct
10	Correct	1403 ms	107680 KB	Output is correct
11	Correct	1 ms	204 KB	Output is correct

Subtask #3

26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	2 ms	588 KB	Output is correct
3	Correct	2 ms	588 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	460 KB	Output is correct
6	Correct	2 ms	588 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	2 ms	588 KB	Output is correct
10	Correct	2 ms	460 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	1110 ms	37488 KB	Output is correct
13	Correct	1382 ms	15044 KB	Output is correct
14	Correct	775 ms	3616 KB	Output is correct
15	Correct	1660 ms	22664 KB	Output is correct
16	Correct	381 ms	52876 KB	Output is correct
17	Correct	2692 ms	214772 KB	Output is correct
18	Correct	3096 ms	226744 KB	Output is correct
19	Correct	3070 ms	226740 KB	Output is correct
20	Correct	2983 ms	225788 KB	Output is correct
21	Correct	1 ms	300 KB	Output is correct

Subtask #4

0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	296 KB	Output is correct
2	Correct	2 ms	588 KB	Output is correct
3	Correct	2 ms	588 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	460 KB	Output is correct
6	Correct	2 ms	556 KB	Output is correct
7	Correct	1 ms	332 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	2 ms	588 KB	Output is correct
10	Correct	2 ms	460 KB	Output is correct
11	Correct	1 ms	300 KB	Output is correct
12	Correct	964 ms	48476 KB	Output is correct
13	Correct	719 ms	39400 KB	Output is correct
14	Correct	1447 ms	108944 KB	Output is correct
15	Correct	1484 ms	108744 KB	Output is correct
16	Correct	1270 ms	109608 KB	Output is correct
17	Correct	1442 ms	111004 KB	Output is correct
18	Correct	1399 ms	108404 KB	Output is correct
19	Correct	1095 ms	39120 KB	Output is correct
20	Correct	1374 ms	16880 KB	Output is correct
21	Correct	782 ms	5112 KB	Output is correct
22	Correct	1648 ms	24464 KB	Output is correct
23	Correct	370 ms	54404 KB	Output is correct
24	Correct	2691 ms	215188 KB	Output is correct
25	Correct	3080 ms	227288 KB	Output is correct
26	Correct	3106 ms	227320 KB	Output is correct
27	Correct	2997 ms	226496 KB	Output is correct
28	Runtime error	438 ms	256004 KB	Execution killed with signal 9
29	Halted	0 ms	0 KB	-

Subtask #5

0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	204 KB	Output is correct
2	Correct	2 ms	588 KB	Output is correct
3	Correct	2 ms	636 KB	Output is correct
4	Correct	1 ms	204 KB	Output is correct
5	Correct	1 ms	424 KB	Output is correct
6	Correct	2 ms	588 KB	Output is correct
7	Correct	1 ms	304 KB	Output is correct
8	Correct	1 ms	332 KB	Output is correct
9	Correct	2 ms	588 KB	Output is correct
10	Correct	2 ms	460 KB	Output is correct
11	Correct	1 ms	332 KB	Output is correct
12	Correct	950 ms	47804 KB	Output is correct
13	Correct	710 ms	39604 KB	Output is correct
14	Correct	1445 ms	107620 KB	Output is correct
15	Correct	1470 ms	107368 KB	Output is correct
16	Correct	1257 ms	108332 KB	Output is correct
17	Correct	1444 ms	109812 KB	Output is correct
18	Correct	1378 ms	107048 KB	Output is correct
19	Correct	1120 ms	37808 KB	Output is correct
20	Correct	1374 ms	15428 KB	Output is correct
21	Correct	770 ms	3840 KB	Output is correct
22	Correct	1687 ms	23004 KB	Output is correct
23	Correct	379 ms	52988 KB	Output is correct
24	Correct	2670 ms	213956 KB	Output is correct
25	Correct	3092 ms	225832 KB	Output is correct
26	Correct	3095 ms	226000 KB	Output is correct
27	Correct	3120 ms	225056 KB	Output is correct
28	Runtime error	434 ms	256004 KB	Execution killed with signal 9
29	Halted	0 ms	0 KB	-