oj.uz

Submission #399486

# Submission time Handle Problem Language Result Execution time Memory
399486 2021-05-05T22:25:57 Z cfalas Game (IOI13_game) C++14
63 / 100
 11557 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;
    			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;
    		}
     
    		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]);
    			else{
    				create_children(ind, 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);
    				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) {
    	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:126:13: warning: inline variables are only available with '-std=c++17' or '-std=gnu++17'
  126 |      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 3 ms 588 KB Output is correct
3 Correct 3 ms 552 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 2 ms 460 KB Output is correct
10 Correct 1 ms 424 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 288 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1012 ms 39296 KB Output is correct
5 Correct 757 ms 35120 KB Output is correct
6 Correct 1578 ms 94028 KB Output is correct
7 Correct 1513 ms 97116 KB Output is correct
8 Correct 1315 ms 93976 KB Output is correct
9 Correct 1594 ms 98572 KB Output is correct
10 Correct 1477 ms 96436 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 588 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 2 ms 424 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 424 KB Output is correct
10 Correct 2 ms 412 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 4458 ms 24948 KB Output is correct
13 Correct 4250 ms 11496 KB Output is correct
14 Correct 864 ms 4152 KB Output is correct
15 Correct 6026 ms 15296 KB Output is correct
16 Correct 7953 ms 29840 KB Output is correct
17 Correct 4531 ms 143924 KB Output is correct
18 Correct 9618 ms 152776 KB Output is correct
19 Correct 10264 ms 149732 KB Output is correct
20 Correct 11557 ms 148320 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 292 KB Output is correct
2 Correct 3 ms 576 KB Output is correct
3 Correct 3 ms 548 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 428 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 1 ms 460 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 1047 ms 39480 KB Output is correct
13 Correct 766 ms 35588 KB Output is correct
14 Correct 1602 ms 94232 KB Output is correct
15 Correct 1621 ms 97228 KB Output is correct
16 Correct 1392 ms 94280 KB Output is correct
17 Correct 1627 ms 98776 KB Output is correct
18 Correct 1492 ms 96616 KB Output is correct
19 Correct 4396 ms 23980 KB Output is correct
20 Correct 4265 ms 10552 KB Output is correct
21 Correct 839 ms 2848 KB Output is correct
22 Correct 6399 ms 14532 KB Output is correct
23 Correct 8505 ms 29080 KB Output is correct
24 Correct 4479 ms 144024 KB Output is correct
25 Correct 9871 ms 152712 KB Output is correct
26 Correct 10218 ms 149336 KB Output is correct
27 Correct 11393 ms 148784 KB Output is correct
28 Runtime error 420 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 3 ms 460 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 332 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 1 ms 460 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1028 ms 38244 KB Output is correct
13 Correct 780 ms 34464 KB Output is correct
14 Correct 1554 ms 93904 KB Output is correct
15 Correct 1531 ms 97000 KB Output is correct
16 Correct 1326 ms 93832 KB Output is correct
17 Correct 1542 ms 98372 KB Output is correct
18 Correct 1478 ms 96320 KB Output is correct
19 Correct 4248 ms 23652 KB Output is correct
20 Correct 4161 ms 10228 KB Output is correct
21 Correct 846 ms 2452 KB Output is correct
22 Correct 6108 ms 14100 KB Output is correct
23 Correct 8219 ms 28672 KB Output is correct
24 Correct 4193 ms 143796 KB Output is correct
25 Correct 9197 ms 152568 KB Output is correct
26 Correct 9499 ms 149432 KB Output is correct
27 Correct 10716 ms 148908 KB Output is correct
28 Runtime error 407 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -