oj.uz

Submission #399570

# Submission time Handle Problem Language Result Execution time Memory
399570 2021-05-06T06:22:00 Z cfalas Game (IOI13_game) C++14
63 / 100
 1626 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;
			}
		}


	};
	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:103:9: warning: inline variables are only available with '-std=c++17' or '-std=gnu++17'
  103 |  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 460 KB Output is correct
3 Correct 2 ms 460 KB Output is correct
4 Correct 1 ms 296 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 300 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 424 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 610 ms 18864 KB Output is correct
5 Correct 581 ms 18624 KB Output is correct
6 Correct 810 ms 20208 KB Output is correct
7 Correct 885 ms 21188 KB Output is correct
8 Correct 615 ms 15952 KB Output is correct
9 Correct 876 ms 20040 KB Output is correct
10 Correct 841 ms 19784 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 460 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 296 KB Output is correct
6 Correct 2 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 292 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 895 ms 21708 KB Output is correct
13 Correct 1348 ms 8980 KB Output is correct
14 Correct 337 ms 1380 KB Output is correct
15 Correct 1626 ms 12708 KB Output is correct
16 Correct 268 ms 26824 KB Output is correct
17 Correct 934 ms 16816 KB Output is correct
18 Correct 1572 ms 27680 KB Output is correct
19 Correct 1339 ms 27692 KB Output is correct
20 Correct 1297 ms 26948 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 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 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 600 ms 18800 KB Output is correct
13 Correct 564 ms 18808 KB Output is correct
14 Correct 803 ms 20820 KB Output is correct
15 Correct 877 ms 21456 KB Output is correct
16 Correct 617 ms 16380 KB Output is correct
17 Correct 856 ms 20352 KB Output is correct
18 Correct 825 ms 19784 KB Output is correct
19 Correct 880 ms 22120 KB Output is correct
20 Correct 1341 ms 9356 KB Output is correct
21 Correct 329 ms 1604 KB Output is correct
22 Correct 1596 ms 12972 KB Output is correct
23 Correct 268 ms 27264 KB Output is correct
24 Correct 929 ms 16676 KB Output is correct
25 Correct 1560 ms 27572 KB Output is correct
26 Correct 1342 ms 27704 KB Output is correct
27 Correct 1266 ms 27200 KB Output is correct
28 Runtime error 625 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 2 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 2 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 606 ms 18800 KB Output is correct
13 Correct 566 ms 19024 KB Output is correct
14 Correct 786 ms 20080 KB Output is correct
15 Correct 872 ms 21324 KB Output is correct
16 Correct 592 ms 15900 KB Output is correct
17 Correct 861 ms 20024 KB Output is correct
18 Correct 836 ms 19784 KB Output is correct
19 Correct 897 ms 21820 KB Output is correct
20 Correct 1334 ms 8900 KB Output is correct
21 Correct 329 ms 1440 KB Output is correct
22 Correct 1618 ms 12592 KB Output is correct
23 Correct 271 ms 27044 KB Output is correct
24 Correct 909 ms 16524 KB Output is correct
25 Correct 1573 ms 27268 KB Output is correct
26 Correct 1367 ms 27408 KB Output is correct
27 Correct 1286 ms 26912 KB Output is correct
28 Runtime error 633 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -