oj.uz

Submission #399437

# Submission time Handle Problem Language Result Execution time Memory
399437 2021-05-05T19:36:26 Z cfalas Game (IOI13_game) C++14
10 / 100
 13000 ms 106584 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;
vector<ii> changed;
static map<ii, int> mapper[100000];

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;
			int left=-1;
			int right=-1;
			node() {val=0, left=-1, right=-1;}
			node(T v) {val=v, right=-1, left=-1;}
		};
		int parent;
		vector<node> seg;
		T RAND_VALUE=0;
		seg_tree(){seg.assign(1, node());}

		inline node merge(node& par, node& a, node& b){
			node ret;
			ret.left = par.left, ret.right = par.right;
			ret.val = gcd(a.val , b.val);
			return ret;
		}

		inline void update_node(int ind, T val, int l, int r){
			//cout<<"Node "<<parent<<" "<<ind<<" "<<l<<" "<<r<<" "<<val<<endl;
			//seg[ind].val = 1-seg[ind].val;
			seg[ind].val = val;
			changed.push_back({l,r});
		}

		inline void create_children(int ind, int l, int r){
			if(seg[ind].left==-1) seg[ind].left=seg.size(), mapper[parent][{l,MID}] = seg[ind].left, seg.push_back(node());
			if(seg[ind].right==-1) seg[ind].right=seg.size(), mapper[parent][{MID+1,r}] = seg[ind].right, seg.push_back(node());
		}

		void print(int l=0, int r=M-1, int ind=0){
			cout<<"("<<l<<" "<<r<<" "<<ind<<": "<<seg[ind].val<<") ";
			if(seg[ind].left!=-1) print(l, MID, seg[ind].left);
			if(seg[ind].right!=-1) print(MID+1, r, seg[ind].right);
		}

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

				seg[ind] = merge(seg[ind], seg[seg[ind].left], seg[seg[ind].right]);
			}
		}

		void update(int x, T val, int l=0, int r=M-1, int ind=0){
			if(x==l && r==x) update_node(ind, val,l,r);
			else if(x<l || r<x) return;
			else{
				create_children(ind, l, r);
				changed.push_back({l,r});
				update(x,val,l,MID,seg[ind].left);
				update(x,val,MID+1,r,seg[ind].right);
				seg[ind] = merge(seg[ind], seg[seg[ind].left], seg[seg[ind].right]);
			}
		}

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

		map<int, T> leaves;

		void create_leaves(int l=0, int r=N-1, int ind=0){
			if(l==r) leaves[l] = seg[ind].val;
			if(seg[ind].left!=-1) create_leaves(l, MID, seg[ind].left);
			if(seg[ind].right!=-1) create_leaves(MID+1, r, seg[ind].right);
		}

		map<int, T> get_leaves(){
			//cout<<"Getting leaves of "<<parent<<endl;
			leaves.clear();
			create_leaves();
			return leaves;
		}


	};
	struct node{
		seg_tree<Q> val;
		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()); seg2d[0].val.parent = 0;}

	inline void merge(node &par, node &a, node &b, int ind){
		/*
		cout<<"MERGING "<<par.left<<": ";
		a.val.print();
		cout<<"\nWITH "<<par.right<<": ";
		b.val.print();
		cout<<endl;
		cout<<"CHANGE ";
		FOA(v,changed) cout<<"("<<v.F<<" "<<v.S<<") ";
		cout<<endl;
		*/
		//if(par.val.seg.size()==1 && (a.val.seg.size()+b.val.seg.size()>2)){
			par.val = a.val;
			par.val.parent = ind;
			vi ar(N);
			map<int, Q> leaves_a = a.val.get_leaves();
			map<int, Q> leaves_b = b.val.get_leaves();
			//cout<<"LEAVES A: "; FOA(v,leaves_a) cout<<"("<<v.F<<" "<<v.S<<") "; cout<<endl;
			//cout<<"LEAVES B: "; FOA(v,leaves_b) cout<<"("<<v.F<<" "<<v.S<<") "; cout<<endl;
			FOA(v,leaves_a){
				if(leaves_b[v.F]) leaves_a[v.F] = gcd(v.S, leaves_b[v.F]);
			}
			leaves_a.insert(leaves_b.begin(), leaves_b.end());
			//cout<<"LEAVES BOTH: "; FOA(v,leaves_a) cout<<"("<<v.F<<" "<<v.S<<") "; cout<<endl;
			FOA(v,leaves_a){
				//cout<<v.F<<" "<<v.S<<endl;
				par.val.update(v.F, v.S);
			}
			assert(a.val.parent==seg2d[ind].left);
		/*}
		else{
			//assert(a.val.parent==seg2d[ind].left);
			FOA(v,changed){
				cout<<v.F<<" "<<v.S<<endl;
				par.val.seg[mapper[ind][v]].val = gcd(a.val.seg[mapper[seg2d[ind].left][v]].val , b.val.seg[mapper[seg2d[ind].right][v]].val);
			}
		}
		*/
		//cout<<"RESULT OF MERGE ";
		//par.val.print();
		//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());
			seg2d.back().val.parent = seg2d[ind].left;
			mapper[seg2d[ind].left][{0,M-1}] = 0;
		}
		if(seg2d[ind].right==-1){
			seg2d[ind].right=seg2d.size();
			seg2d.push_back(node());
			seg2d.back().val.parent = seg2d[ind].right;
			mapper[seg2d[ind].right][{0,M-1}] = 0;
		}
		//if(seg2d[ind].right==-1) seg2d[ind].right=seg2d.size(), seg2d.push_back(node()), seg2d.back().val.parent = seg2d[ind].right;
	}

	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);
			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 = max(R, C);
	seg.N = max(R,C);
}

void update(int P, int Q, long long K) {
	changed.clear();
	seg.update(P,Q,K);
	//seg.print();
	/*
	FOR(i,M){
		FOR(j,M) seg.query(i,i,j,j);
		//FOR(j,M) cout<<setw(1)<<seg.query(i,i,j,j);
		//cout<<endl;
	}
	*/
	//cout<<endl;
}

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

/*
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	int q;
	cin>>n>>q;
	init(n,n);
	string s[n];
	vector<vector<ll> > a(n, vi(n, 0));
	FOR(i,n) cin>>s[i];

	FOR(i,n) FOR(j,n){
		if(s[i][j]=='*') a[i][j] = 1;
		else a[i][j] = 0;
	}
	seg.build(a);
	while(q--){
		cin>>t;
		if(t==1){
			int x, y;
			cin>>x>>y;
			update(x-1,y-1, 1);
		}
		else{
			int x1, y1, x2, y2;
			cin>>x1>>y1>>x2>>y2;
			cout<<seg.query(x1-1,x2-1, y1-1, y2-1)<<"\n";
		}
	}
}
*/

Compilation message

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

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 17 ms 5744 KB Output is correct
3 Correct 21 ms 5864 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 4 ms 5328 KB Output is correct
6 Correct 16 ms 5600 KB Output is correct
7 Correct 4 ms 5116 KB Output is correct
8 Correct 4 ms 5132 KB Output is correct
9 Correct 15 ms 5504 KB Output is correct
10 Correct 8 ms 5580 KB Output is correct
11 Correct 9 ms 5120 KB Output is correct
12 Correct 4 ms 4940 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 3 ms 4940 KB Output is correct
3 Correct 4 ms 5068 KB Output is correct
4 Execution timed out 13073 ms 106364 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 17 ms 5656 KB Output is correct
3 Correct 20 ms 5836 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 5 ms 5380 KB Output is correct
6 Correct 16 ms 5452 KB Output is correct
7 Correct 4 ms 5124 KB Output is correct
8 Correct 4 ms 5196 KB Output is correct
9 Correct 15 ms 5528 KB Output is correct
10 Correct 8 ms 5484 KB Output is correct
11 Correct 9 ms 5124 KB Output is correct
12 Execution timed out 13079 ms 36456 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4940 KB Output is correct
2 Correct 17 ms 5708 KB Output is correct
3 Correct 21 ms 5868 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 5 ms 5324 KB Output is correct
6 Correct 16 ms 5440 KB Output is correct
7 Correct 4 ms 5072 KB Output is correct
8 Correct 4 ms 5196 KB Output is correct
9 Correct 15 ms 5484 KB Output is correct
10 Correct 8 ms 5580 KB Output is correct
11 Correct 9 ms 5196 KB Output is correct
12 Execution timed out 13088 ms 106584 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4996 KB Output is correct
2 Correct 17 ms 5744 KB Output is correct
3 Correct 21 ms 5836 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 5 ms 5324 KB Output is correct
6 Correct 16 ms 5452 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5196 KB Output is correct
9 Correct 16 ms 5452 KB Output is correct
10 Correct 8 ms 5512 KB Output is correct
11 Correct 9 ms 5196 KB Output is correct
12 Execution timed out 13097 ms 106380 KB Time limit exceeded
13 Halted 0 ms 0 KB -