oj.uz

Submission #399471

# Submission time Handle Problem Language Result Execution time Memory
399471 2021-05-05T21:08:10 Z cfalas Game (IOI13_game) C++14
10 / 100
 10621 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;
vector<ii> changed;
static map<ii, int> mapper[101000];

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());}

		unordered_map<int, T> leaves;
		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;
			leaves[l] = val;
			if(val==0) leaves.erase(l);
			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));
			}
		}


	};
	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.parent = ind;
		/*
		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(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(v.F, val);
		}
		//cout<<"LEAVES BOTH: "; FOA(v,leaves_a) cout<<"("<<v.F<<" "<<v.S<<") "; cout<<endl;
		/*}
		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 = R;
	seg.N = C;
}

void update(int P, int Q, long long K) {
	changed.clear();
	seg.update(Q,P,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(Q,V,P,U);
}

/*
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:130:9: warning: inline variables are only available with '-std=c++17' or '-std=gnu++17'
  130 |  static inline int N;
      |         ^~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 7 ms 5836 KB Output is correct
3 Correct 7 ms 5812 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 6 ms 5452 KB Output is correct
6 Correct 6 ms 5580 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5196 KB Output is correct
9 Correct 6 ms 5580 KB Output is correct
10 Correct 5 ms 5552 KB Output is correct
11 Correct 4 ms 5196 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 5040 KB Output is correct
4 Correct 1187 ms 89532 KB Output is correct
5 Correct 920 ms 67576 KB Output is correct
6 Runtime error 259 ms 138056 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 5048 KB Output is correct
2 Correct 7 ms 5836 KB Output is correct
3 Correct 7 ms 5836 KB Output is correct
4 Correct 3 ms 4940 KB Output is correct
5 Correct 5 ms 5424 KB Output is correct
6 Correct 6 ms 5580 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5196 KB Output is correct
9 Correct 6 ms 5580 KB Output is correct
10 Correct 5 ms 5452 KB Output is correct
11 Correct 4 ms 5196 KB Output is correct
12 Correct 5897 ms 69216 KB Output is correct
13 Correct 5224 ms 33196 KB Output is correct
14 Correct 914 ms 13488 KB Output is correct
15 Correct 7996 ms 46208 KB Output is correct
16 Correct 10621 ms 93684 KB Output is correct
17 Runtime error 1792 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 4 ms 4940 KB Output is correct
2 Correct 7 ms 5836 KB Output is correct
3 Correct 7 ms 5808 KB Output is correct
4 Correct 4 ms 4940 KB Output is correct
5 Correct 5 ms 5452 KB Output is correct
6 Correct 6 ms 5580 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5196 KB Output is correct
9 Correct 6 ms 5580 KB Output is correct
10 Correct 5 ms 5452 KB Output is correct
11 Correct 4 ms 5196 KB Output is correct
12 Correct 1205 ms 89468 KB Output is correct
13 Correct 919 ms 67600 KB Output is correct
14 Runtime error 255 ms 138084 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 4940 KB Output is correct
2 Correct 7 ms 5836 KB Output is correct
3 Correct 7 ms 5836 KB Output is correct
4 Correct 4 ms 4956 KB Output is correct
5 Correct 5 ms 5452 KB Output is correct
6 Correct 6 ms 5580 KB Output is correct
7 Correct 4 ms 5068 KB Output is correct
8 Correct 4 ms 5196 KB Output is correct
9 Correct 6 ms 5616 KB Output is correct
10 Correct 5 ms 5452 KB Output is correct
11 Correct 4 ms 5168 KB Output is correct
12 Correct 1225 ms 89548 KB Output is correct
13 Correct 919 ms 67584 KB Output is correct
14 Runtime error 257 ms 137864 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -