oj.uz

Submission #399554

# Submission time Handle Problem Language Result Execution time Memory
399554 2021-05-06T05:27:24 Z cfalas Game (IOI13_game) C++14
63 / 100
 3120 ms 256004 KB 
#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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -