oj.uz

Submission #399567

# Submission time Handle Problem Language Result Execution time Memory
399567 2021-05-06T06:14:33 Z cfalas Game (IOI13_game) C++14
37 / 100
 2073 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{
				create_children();
				if(x<=MID) left->update(x,val_n,l,MID);
				else right->update(x,val_n,MID+1,r);
				val = gcd(left->val, right->val);
			}
		}

		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{
				create_children();
				return  gcd(left->query(rl,rr,l,MID) , right->query(rl,rr,MID+1,r));
			}
		}


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

	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());
		}
		if(seg2d[ind].right==-1){
			seg2d[ind].right=seg2d.size();
			seg2d.push_back(node());
		}
	}

	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);
			Q g = seg2d[seg2d[ind].left].val.query(x, x);
			g = gcd(g, seg2d[seg2d[ind].right].val.query(x, x));
			if(seg2d[ind].val.query(x, x)!= g){
				seg2d[ind].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, 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);
}

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

Compilation message

game.cpp:93:9: warning: inline variables are only available with '-std=c++17' or '-std=gnu++17'
   93 |  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 716 KB Output is correct
3 Correct 2 ms 716 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 472 KB Output is correct
6 Correct 2 ms 716 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 588 KB Output is correct
10 Correct 1 ms 588 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 910 ms 46848 KB Output is correct
5 Correct 671 ms 37292 KB Output is correct
6 Correct 1440 ms 122808 KB Output is correct
7 Correct 1489 ms 122376 KB Output is correct
8 Correct 1295 ms 126172 KB Output is correct
9 Correct 1485 ms 125692 KB Output is correct
10 Correct 1395 ms 121916 KB Output is correct
11 Correct 1 ms 204 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 2 ms 716 KB Output is correct
3 Correct 2 ms 716 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 716 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 588 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 1100 ms 46792 KB Output is correct
13 Correct 1345 ms 17076 KB Output is correct
14 Correct 833 ms 2648 KB Output is correct
15 Correct 1646 ms 27576 KB Output is correct
16 Correct 346 ms 69892 KB Output is correct
17 Runtime error 2051 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 1 ms 204 KB Output is correct
2 Correct 2 ms 716 KB Output is correct
3 Correct 2 ms 716 KB Output is correct
4 Correct 1 ms 276 KB Output is correct
5 Correct 2 ms 460 KB Output is correct
6 Correct 2 ms 716 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 588 KB Output is correct
10 Correct 2 ms 588 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 923 ms 46944 KB Output is correct
13 Correct 661 ms 37216 KB Output is correct
14 Correct 1446 ms 122576 KB Output is correct
15 Correct 1484 ms 122380 KB Output is correct
16 Correct 1279 ms 126180 KB Output is correct
17 Correct 1443 ms 125664 KB Output is correct
18 Correct 1407 ms 121988 KB Output is correct
19 Correct 1116 ms 46768 KB Output is correct
20 Correct 1339 ms 17240 KB Output is correct
21 Correct 831 ms 2704 KB Output is correct
22 Correct 1661 ms 27596 KB Output is correct
23 Correct 351 ms 69848 KB Output is correct
24 Runtime error 2073 ms 256004 KB Execution killed with signal 9
25 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 716 KB Output is correct
3 Correct 2 ms 716 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 464 KB Output is correct
6 Correct 2 ms 716 KB Output is correct
7 Correct 1 ms 336 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 2 ms 588 KB Output is correct
10 Correct 1 ms 588 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 907 ms 46916 KB Output is correct
13 Correct 691 ms 37224 KB Output is correct
14 Correct 1451 ms 122608 KB Output is correct
15 Correct 1458 ms 122396 KB Output is correct
16 Correct 1247 ms 126060 KB Output is correct
17 Correct 1443 ms 125676 KB Output is correct
18 Correct 1393 ms 121924 KB Output is correct
19 Correct 1113 ms 46844 KB Output is correct
20 Correct 1340 ms 17112 KB Output is correct
21 Correct 833 ms 2740 KB Output is correct
22 Correct 1614 ms 27504 KB Output is correct
23 Correct 347 ms 69928 KB Output is correct
24 Runtime error 2028 ms 256004 KB Execution killed with signal 9
25 Halted 0 ms 0 KB -