oj.uz

Submission #399555

# Submission time Handle Problem Language Result Execution time Memory
399555 2021-05-06T05:28:53 Z cfalas Game (IOI13_game) C++14
63 / 100
 3119 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();}

		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;
			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:124:3: warning: "/*" within comment [-Wcomment]
  124 |   /*
      |    
game.cpp:150:3: warning: "/*" within comment [-Wcomment]
  150 |   /*
      |    
game.cpp:118:9: warning: inline variables are only available with '-std=c++17' or '-std=gnu++17'
  118 |  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 660 KB Output is correct
3 Correct 3 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 460 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 460 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 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1002 ms 37736 KB Output is correct
5 Correct 704 ms 30160 KB Output is correct
6 Correct 1504 ms 92544 KB Output is correct
7 Correct 1431 ms 92196 KB Output is correct
8 Correct 1212 ms 95116 KB Output is correct
9 Correct 1443 ms 94500 KB Output is correct
10 Correct 1347 ms 92108 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 592 KB Output is correct
3 Correct 2 ms 588 KB Output is correct
4 Correct 1 ms 228 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 348 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 2 ms 572 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1039 ms 32708 KB Output is correct
13 Correct 1333 ms 11764 KB Output is correct
14 Correct 742 ms 1980 KB Output is correct
15 Correct 1625 ms 18884 KB Output is correct
16 Correct 332 ms 47172 KB Output is correct
17 Correct 2685 ms 210020 KB Output is correct
18 Correct 3119 ms 219972 KB Output is correct
19 Correct 3063 ms 220052 KB Output is correct
20 Correct 2939 ms 219204 KB Output is correct
21 Correct 1 ms 204 KB Output is correct

Subtask #4
0 / 17.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 460 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 460 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 903 ms 37780 KB Output is correct
13 Correct 671 ms 30244 KB Output is correct
14 Correct 1386 ms 92420 KB Output is correct
15 Correct 1417 ms 92196 KB Output is correct
16 Correct 1214 ms 95144 KB Output is correct
17 Correct 1482 ms 94788 KB Output is correct
18 Correct 1340 ms 91896 KB Output is correct
19 Correct 1057 ms 32836 KB Output is correct
20 Correct 1354 ms 11816 KB Output is correct
21 Correct 787 ms 2012 KB Output is correct
22 Correct 1644 ms 18964 KB Output is correct
23 Correct 325 ms 47224 KB Output is correct
24 Correct 2725 ms 210116 KB Output is correct
25 Correct 3072 ms 220104 KB Output is correct
26 Correct 3074 ms 220060 KB Output is correct
27 Correct 3014 ms 219280 KB Output is correct
28 Runtime error 446 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 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 460 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 913 ms 37756 KB Output is correct
13 Correct 660 ms 30128 KB Output is correct
14 Correct 1382 ms 92564 KB Output is correct
15 Correct 1446 ms 92236 KB Output is correct
16 Correct 1223 ms 95004 KB Output is correct
17 Correct 1420 ms 94628 KB Output is correct
18 Correct 1338 ms 91876 KB Output is correct
19 Correct 1072 ms 32676 KB Output is correct
20 Correct 1337 ms 11724 KB Output is correct
21 Correct 751 ms 1988 KB Output is correct
22 Correct 1636 ms 18996 KB Output is correct
23 Correct 317 ms 47172 KB Output is correct
24 Correct 2659 ms 209960 KB Output is correct
25 Correct 3033 ms 220072 KB Output is correct
26 Correct 3018 ms 220088 KB Output is correct
27 Correct 2989 ms 219220 KB Output is correct
28 Runtime error 453 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -