oj.uz

Submission #399564

# Submission time Handle Problem Language Result Execution time Memory
399564 2021-05-06T05:48:10 Z cfalas Game (IOI13_game) C++14
10 / 100
 2093 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{
		T val;
		seg_tree* left=nullptr;
		seg_tree* right=nullptr;

		T RAND_VALUE=0;

		inline void merge(){
			val = gcd(left->val , right->val);
		}

		inline void update_node(T val_n, int l, int r){
			val = val_n;
		}

		inline void create_children(){
			if(left==nullptr) left= new seg_tree();
			if(right==nullptr) right = new seg_tree();
		}

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

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

				merge();
			}
		}
		*/

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

		T query(int rl, int rr, int l=0, int r=M-1){
			if(rl<=l && r<=rr) return val;
			else if(rl>r || l>rr) return RAND_VALUE;
			else{
				create_children();
				return  gcd(left->query(rl, rr, l, MID) , right->query(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(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(x, x);
			g = gcd(g, seg2d[seg2d[ind].right].val->query(x, x));
			if(seg2d[ind].val->query(x, x)!= g){
				seg2d[ind].val->update(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(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:120:3: warning: "/*" within comment [-Wcomment]
  120 |   /*
      |    
game.cpp:146:3: warning: "/*" within comment [-Wcomment]
  146 |   /*
      |    
game.cpp:114:9: warning: inline variables are only available with '-std=c++17' or '-std=gnu++17'
  114 |  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 716 KB Output is correct
3 Correct 2 ms 716 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 716 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 1 ms 588 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1 ms 204 KB Output is correct

Subtask #2
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 Incorrect 973 ms 49344 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Correct 2 ms 716 KB Output is correct
3 Correct 2 ms 716 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 464 KB Output is correct
6 Correct 2 ms 716 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 588 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1083 ms 46828 KB Output is correct
13 Correct 1328 ms 17132 KB Output is correct
14 Correct 776 ms 2788 KB Output is correct
15 Correct 1642 ms 27624 KB Output is correct
16 Correct 353 ms 69956 KB Output is correct
17 Runtime error 2093 ms 256004 KB Execution killed with signal 9
18 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 716 KB Output is correct
3 Correct 2 ms 716 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 716 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 588 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Incorrect 960 ms 49160 KB Output isn't correct
13 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 716 KB Output is correct
3 Correct 2 ms 716 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 716 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 1 ms 592 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Incorrect 967 ms 49072 KB Output isn't correct
13 Halted 0 ms 0 KB -