oj.uz

Submission #399575

# Submission time Handle Problem Language Result Execution time Memory
399575 2021-05-06T06:37:31 Z cfalas Game (IOI13_game) C++14
63 / 100
 1631 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{
		T val=0;
		seg_tree* left=nullptr;
		seg_tree* right=nullptr;

		T RAND_VALUE=0;

		inline void create_children(){
			if(left==nullptr) left= new seg_tree();
			if(right==nullptr) right = new seg_tree();
		}

		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(x<=MID){
					if(left==nullptr) left = new seg_tree();
					left->update(x,val_n,l,MID);
				}
				else{
					if(right==nullptr) right = new seg_tree();
					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{
				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:101:9: warning: inline variables are only available with '-std=c++17' or '-std=gnu++17'
  101 |  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 460 KB Output is correct
3 Correct 1 ms 460 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 460 KB Output is correct
7 Correct 1 ms 208 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 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 519 ms 17420 KB Output is correct
5 Correct 495 ms 17720 KB Output is correct
6 Correct 604 ms 14756 KB Output is correct
7 Correct 721 ms 14504 KB Output is correct
8 Correct 438 ms 9492 KB Output is correct
9 Correct 679 ms 14624 KB Output is correct
10 Correct 651 ms 14224 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 332 KB Output is correct
3 Correct 1 ms 460 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 460 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 208 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 332 KB Output is correct
12 Correct 859 ms 21488 KB Output is correct
13 Correct 1375 ms 8564 KB Output is correct
14 Correct 295 ms 996 KB Output is correct
15 Correct 1631 ms 12400 KB Output is correct
16 Correct 265 ms 26660 KB Output is correct
17 Correct 860 ms 16292 KB Output is correct
18 Correct 1544 ms 27052 KB Output is correct
19 Correct 1349 ms 27240 KB Output is correct
20 Correct 1238 ms 26552 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 460 KB Output is correct
3 Correct 2 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 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 539 ms 17412 KB Output is correct
13 Correct 493 ms 17744 KB Output is correct
14 Correct 643 ms 14704 KB Output is correct
15 Correct 726 ms 14608 KB Output is correct
16 Correct 446 ms 9408 KB Output is correct
17 Correct 772 ms 14684 KB Output is correct
18 Correct 700 ms 14144 KB Output is correct
19 Correct 866 ms 21468 KB Output is correct
20 Correct 1364 ms 8608 KB Output is correct
21 Correct 290 ms 988 KB Output is correct
22 Correct 1607 ms 12404 KB Output is correct
23 Correct 268 ms 26872 KB Output is correct
24 Correct 887 ms 16400 KB Output is correct
25 Correct 1604 ms 27024 KB Output is correct
26 Correct 1366 ms 27400 KB Output is correct
27 Correct 1298 ms 26556 KB Output is correct
28 Runtime error 711 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 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 460 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 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 528 ms 18504 KB Output is correct
13 Correct 498 ms 18900 KB Output is correct
14 Correct 710 ms 15532 KB Output is correct
15 Correct 802 ms 15260 KB Output is correct
16 Correct 443 ms 10236 KB Output is correct
17 Correct 768 ms 15476 KB Output is correct
18 Correct 688 ms 14912 KB Output is correct
19 Correct 899 ms 22160 KB Output is correct
20 Correct 1371 ms 9384 KB Output is correct
21 Correct 298 ms 1868 KB Output is correct
22 Correct 1590 ms 13184 KB Output is correct
23 Correct 277 ms 27464 KB Output is correct
24 Correct 893 ms 17048 KB Output is correct
25 Correct 1618 ms 27792 KB Output is correct
26 Correct 1381 ms 27960 KB Output is correct
27 Correct 1299 ms 27208 KB Output is correct
28 Runtime error 711 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -