oj.uz

Submission #399472

# Submission time Handle Problem Language Result Execution time Memory
399472 2021-05-05T21:15:27 Z cfalas Game (IOI13_game) C++14
10 / 100
 10317 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[401000];

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 11 ms 19020 KB Output is correct
2 Correct 14 ms 19916 KB Output is correct
3 Correct 14 ms 19900 KB Output is correct
4 Correct 11 ms 19020 KB Output is correct
5 Correct 12 ms 19516 KB Output is correct
6 Correct 13 ms 19660 KB Output is correct
7 Correct 11 ms 19132 KB Output is correct
8 Correct 11 ms 19312 KB Output is correct
9 Correct 13 ms 19644 KB Output is correct
10 Correct 12 ms 19660 KB Output is correct
11 Correct 11 ms 19216 KB Output is correct
12 Correct 12 ms 19020 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 19056 KB Output is correct
2 Correct 11 ms 19020 KB Output is correct
3 Correct 11 ms 19148 KB Output is correct
4 Correct 1177 ms 100452 KB Output is correct
5 Correct 932 ms 81640 KB Output is correct
6 Runtime error 1788 ms 256004 KB Execution killed with signal 9
7 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19020 KB Output is correct
2 Correct 17 ms 19904 KB Output is correct
3 Correct 16 ms 19960 KB Output is correct
4 Correct 12 ms 19020 KB Output is correct
5 Correct 14 ms 19516 KB Output is correct
6 Correct 15 ms 19660 KB Output is correct
7 Correct 13 ms 19148 KB Output is correct
8 Correct 13 ms 19256 KB Output is correct
9 Correct 15 ms 19596 KB Output is correct
10 Correct 14 ms 19660 KB Output is correct
11 Correct 13 ms 19276 KB Output is correct
12 Correct 5856 ms 80304 KB Output is correct
13 Correct 5182 ms 44744 KB Output is correct
14 Correct 923 ms 24196 KB Output is correct
15 Correct 8010 ms 56960 KB Output is correct
16 Correct 10317 ms 104556 KB Output is correct
17 Runtime error 1557 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 13 ms 19016 KB Output is correct
2 Correct 16 ms 19900 KB Output is correct
3 Correct 15 ms 19916 KB Output is correct
4 Correct 12 ms 19020 KB Output is correct
5 Correct 13 ms 19532 KB Output is correct
6 Correct 15 ms 19612 KB Output is correct
7 Correct 13 ms 19128 KB Output is correct
8 Correct 13 ms 19212 KB Output is correct
9 Correct 15 ms 19660 KB Output is correct
10 Correct 14 ms 19656 KB Output is correct
11 Correct 14 ms 19276 KB Output is correct
12 Correct 1175 ms 100116 KB Output is correct
13 Correct 926 ms 81616 KB Output is correct
14 Runtime error 1794 ms 256004 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 19020 KB Output is correct
2 Correct 16 ms 19916 KB Output is correct
3 Correct 16 ms 19936 KB Output is correct
4 Correct 13 ms 19020 KB Output is correct
5 Correct 14 ms 19532 KB Output is correct
6 Correct 15 ms 19664 KB Output is correct
7 Correct 13 ms 19180 KB Output is correct
8 Correct 13 ms 19200 KB Output is correct
9 Correct 15 ms 19644 KB Output is correct
10 Correct 14 ms 19660 KB Output is correct
11 Correct 13 ms 19256 KB Output is correct
12 Correct 1196 ms 100388 KB Output is correct
13 Correct 933 ms 81716 KB Output is correct
14 Runtime error 1790 ms 256004 KB Execution killed with signal 9
15 Halted 0 ms 0 KB -