oj.uz

Submission #399583

# Submission time Handle Problem Language Result Execution time Memory
399583 2021-05-06T07:04:44 Z cfalas Game (IOI13_game) C++14
100 / 100
 4892 ms 100612 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{
		T val=0;
		seg_tree* left=nullptr;
		seg_tree* right=nullptr;

		// chain compression
		T pos=-1;

		T RAND_VALUE=0;

		void print(int l=0, int r=M-1){
			cout<<"("<<l<<" "<<r<<": "<<val<<") ";
			if(left!=nullptr) left->print(l, MID);
			if(right!=nullptr) left->print(MID+1, r);
		}

		void update(int x, T val_n, int l=0, int r=M-1){
			if(x==l && r==x) val = val_n;
			else if(x<l || r<x) return;
			else{
				if(pos>=0){ // already compressed chain, need to push
					if(pos>MID){
						right = new seg_tree();
						right->pos = pos;
						right->val = val;
					}
					else{
						left = new seg_tree();
						left->pos = pos;
						left->val = val;
					}
					pos=-1;
				}
				if(x<=MID){
					if(left==nullptr) left = new seg_tree(), left->pos = x, left->val = val_n;
					else left->update(x,val_n,l,MID);
				}
				else{
					if(right==nullptr) right = new seg_tree(), right->pos = x, right->val = val_n;
					else right->update(x,val_n,MID+1, r);
				}
				T g = 0;
				if(left!=nullptr) g = gcd(g, left->val);
				if(right!=nullptr) g = gcd(g, right->val);
				val = g;
			}
		}

		T query(int rl, int rr, int l=0, int r=M-1){
			if(rl<=l && r<=rr) return val;
			else if(rl>r || l>rr) return RAND_VALUE;
			else{
				if(pos>=0 && rl<=pos && pos<=rr) return val;
				else if(pos>=0) return 0;
				T g = 0;
				if(left!=nullptr) g = gcd(g, left->query(rl,rr,l,MID));
				if(right!=nullptr) g = gcd(g, right->query(rl,rr,MID+1,r));
				return g;
			}
		}


	};

	seg_tree<Q> val;
	seg_tree_2d* left=nullptr;
	seg_tree_2d* right=nullptr;

	static inline int N;
	Q RAND_VALUE_2d=0;

	void print(int l=0, int r=N-1){
		cout<<"L R "<<l<<" "<<r<<" "<<endl;
		//seg2d[ind].val->print();
		cout<<endl;
		if(left!=nullptr) left->print(l, MID);
		if(right!=nullptr) right->print(MID+1, r);
	}

	void update(int y, int x, Q val_n, int l=0, int r=N-1){
		if(y==l && y==r) val.update(x, val_n);
		else if(y<l || r<y) return;
		else{
			if(y<=MID){
				if(left==nullptr) left = new seg_tree_2d;
				left->update(y,x,val_n,l,MID);
			}
			else{
				if(right==nullptr) right = new seg_tree_2d;
				right->update(y,x,val_n,MID+1,r);
			}
			Q g = 0;
			if(left!=nullptr) g = gcd(g, left->val.query(x, x));
			if(right!=nullptr) g = gcd(g, right->val.query(x, x));
			if(val.query(x, x)!= g){
				val.update(x, g);
			}
			//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){
		if(rl<=l && r<=rr) return val.query(xl, xr);
		else if(rl>r || l>rr) return RAND_VALUE_2d;
		else{
			Q g = 0;
			if(left!=nullptr) g = gcd(g, left->query(rl, rr, xl, xr,l,MID));
			if(right!=nullptr) g = gcd(g, right->query(rl,rr,xl,xr,MID+1,r));
			return g;
		}
	}

};

seg_tree_2d<ll> seg;

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

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

Compilation message

game.cpp:114:9: warning: inline variables are only available with '-std=c++17' or '-std=gnu++17'
  114 |  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 1 ms 448 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 296 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 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 204 KB Output is correct
4 Correct 491 ms 12548 KB Output is correct
5 Correct 495 ms 13624 KB Output is correct
6 Correct 594 ms 10988 KB Output is correct
7 Correct 693 ms 10608 KB Output is correct
8 Correct 414 ms 7492 KB Output is correct
9 Correct 663 ms 10680 KB Output is correct
10 Correct 638 ms 10412 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 1 ms 336 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 296 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 817 ms 13248 KB Output is correct
13 Correct 1391 ms 6828 KB Output is correct
14 Correct 317 ms 1840 KB Output is correct
15 Correct 1672 ms 8856 KB Output is correct
16 Correct 224 ms 12384 KB Output is correct
17 Correct 706 ms 7960 KB Output is correct
18 Correct 1265 ms 13012 KB Output is correct
19 Correct 1037 ms 13264 KB Output is correct
20 Correct 977 ms 12636 KB Output is correct
21 Correct 1 ms 204 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 292 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 292 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 493 ms 13508 KB Output is correct
13 Correct 483 ms 13852 KB Output is correct
14 Correct 619 ms 11396 KB Output is correct
15 Correct 698 ms 11244 KB Output is correct
16 Correct 421 ms 7792 KB Output is correct
17 Correct 652 ms 11112 KB Output is correct
18 Correct 631 ms 10780 KB Output is correct
19 Correct 817 ms 13432 KB Output is correct
20 Correct 1405 ms 6844 KB Output is correct
21 Correct 305 ms 2056 KB Output is correct
22 Correct 1677 ms 9112 KB Output is correct
23 Correct 226 ms 12736 KB Output is correct
24 Correct 723 ms 8236 KB Output is correct
25 Correct 1225 ms 13024 KB Output is correct
26 Correct 1082 ms 13480 KB Output is correct
27 Correct 1076 ms 12412 KB Output is correct
28 Correct 571 ms 45868 KB Output is correct
29 Correct 1290 ms 41428 KB Output is correct
30 Correct 3805 ms 41312 KB Output is correct
31 Correct 3537 ms 33572 KB Output is correct
32 Correct 680 ms 1796 KB Output is correct
33 Correct 884 ms 5728 KB Output is correct
34 Correct 295 ms 38336 KB Output is correct
35 Correct 929 ms 20332 KB Output is correct
36 Correct 1864 ms 38708 KB Output is correct
37 Correct 1463 ms 39060 KB Output is correct
38 Correct 1453 ms 38388 KB Output is correct
39 Correct 1193 ms 30080 KB Output is correct
40 Correct 1 ms 300 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 204 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 502 ms 12504 KB Output is correct
13 Correct 485 ms 12864 KB Output is correct
14 Correct 577 ms 10180 KB Output is correct
15 Correct 692 ms 9892 KB Output is correct
16 Correct 424 ms 6808 KB Output is correct
17 Correct 642 ms 9900 KB Output is correct
18 Correct 634 ms 9568 KB Output is correct
19 Correct 814 ms 12364 KB Output is correct
20 Correct 1406 ms 6208 KB Output is correct
21 Correct 303 ms 964 KB Output is correct
22 Correct 1653 ms 8036 KB Output is correct
23 Correct 230 ms 11592 KB Output is correct
24 Correct 697 ms 7120 KB Output is correct
25 Correct 1254 ms 12064 KB Output is correct
26 Correct 1055 ms 11976 KB Output is correct
27 Correct 990 ms 11412 KB Output is correct
28 Correct 585 ms 45980 KB Output is correct
29 Correct 1281 ms 41464 KB Output is correct
30 Correct 3807 ms 41104 KB Output is correct
31 Correct 3539 ms 33696 KB Output is correct
32 Correct 681 ms 1896 KB Output is correct
33 Correct 886 ms 5536 KB Output is correct
34 Correct 305 ms 38340 KB Output is correct
35 Correct 918 ms 20324 KB Output is correct
36 Correct 1836 ms 38768 KB Output is correct
37 Correct 1443 ms 38812 KB Output is correct
38 Correct 1441 ms 38300 KB Output is correct
39 Correct 815 ms 100612 KB Output is correct
40 Correct 2035 ms 84300 KB Output is correct
41 Correct 4892 ms 87580 KB Output is correct
42 Correct 4484 ms 70800 KB Output is correct
43 Correct 539 ms 82336 KB Output is correct
44 Correct 969 ms 1552 KB Output is correct
45 Correct 1191 ms 29876 KB Output is correct
46 Correct 2488 ms 82476 KB Output is correct
47 Correct 2473 ms 82684 KB Output is correct
48 Correct 2393 ms 81988 KB Output is correct
49 Correct 1 ms 204 KB Output is correct