oj.uz

Submission #399485

# Submission time Handle Problem Language Result Execution time Memory
399485 2021-05-05T22:24:45 Z cfalas Game (IOI13_game) C++14
63 / 100
 11320 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<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;
    			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:13: 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 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 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 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 204 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 965 ms 38908 KB Output is correct
5 Correct 767 ms 34696 KB Output is correct
6 Correct 1514 ms 97684 KB Output is correct
7 Correct 1444 ms 100800 KB Output is correct
8 Correct 1279 ms 97392 KB Output is correct
9 Correct 1476 ms 102288 KB Output is correct
10 Correct 1417 ms 100240 KB Output is correct
11 Correct 1 ms 296 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 3 ms 588 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 420 KB Output is correct
6 Correct 2 ms 464 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 460 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 4160 ms 24680 KB Output is correct
13 Correct 4203 ms 11260 KB Output is correct
14 Correct 862 ms 3256 KB Output is correct
15 Correct 5896 ms 15316 KB Output is correct
16 Correct 7711 ms 29776 KB Output is correct
17 Correct 4221 ms 148028 KB Output is correct
18 Correct 9048 ms 157472 KB Output is correct
19 Correct 9026 ms 153924 KB Output is correct
20 Correct 10382 ms 153248 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 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 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 460 KB Output is correct
10 Correct 1 ms 460 KB Output is correct
11 Correct 1 ms 292 KB Output is correct
12 Correct 1004 ms 39660 KB Output is correct
13 Correct 813 ms 35124 KB Output is correct
14 Correct 1524 ms 97764 KB Output is correct
15 Correct 1530 ms 100840 KB Output is correct
16 Correct 1317 ms 97284 KB Output is correct
17 Correct 1557 ms 102216 KB Output is correct
18 Correct 1498 ms 100236 KB Output is correct
19 Correct 4542 ms 26904 KB Output is correct
20 Correct 4213 ms 13348 KB Output is correct
21 Correct 851 ms 6412 KB Output is correct
22 Correct 6068 ms 17824 KB Output is correct
23 Correct 7911 ms 32180 KB Output is correct
24 Correct 4337 ms 147848 KB Output is correct
25 Correct 9589 ms 157248 KB Output is correct
26 Correct 10134 ms 153688 KB Output is correct
27 Correct 11320 ms 153268 KB Output is correct
28 Runtime error 438 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 3 ms 588 KB Output is correct
3 Correct 3 ms 588 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 332 KB Output is correct
9 Correct 3 ms 460 KB Output is correct
10 Correct 2 ms 460 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1025 ms 41036 KB Output is correct
13 Correct 831 ms 35880 KB Output is correct
14 Correct 1596 ms 97744 KB Output is correct
15 Correct 1564 ms 100808 KB Output is correct
16 Correct 1441 ms 97284 KB Output is correct
17 Correct 1665 ms 102332 KB Output is correct
18 Correct 1521 ms 100116 KB Output is correct
19 Correct 4459 ms 27004 KB Output is correct
20 Correct 4253 ms 13380 KB Output is correct
21 Correct 843 ms 6416 KB Output is correct
22 Correct 6288 ms 17740 KB Output is correct
23 Correct 8296 ms 32164 KB Output is correct
24 Correct 4458 ms 147904 KB Output is correct
25 Correct 9780 ms 157304 KB Output is correct
26 Correct 9992 ms 153688 KB Output is correct
27 Correct 11302 ms 153320 KB Output is correct
28 Runtime error 434 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -