oj.uz

Submission #238483

# Submission time Handle Problem Language Result Execution time Memory
238483 2020-06-11T14:06:17 Z figter001 Game (IOI13_game) C++17
63 / 100
 3451 ms 256004 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

#define all(x) (x).begin(), (x).end()
#define fast ios::sync_with_stdio(false);cin.tie(0);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;

const int TO = 1e9 + 1;

int r,c,n;
int p,q;

struct node{
	node *l,*r;
	ll val;
	node(){
		l = r = NULL;
		val = 0;
	}
	void marge(){
		val = __gcd(l->val , r->val);
	}
};

struct node2d{
	node2d *l,*r;
	node *child;
	node2d(){
		l = r = NULL;
		child = new node();
	}
};

node2d *head2d;

void update_range(int at,ll val,node *&n,int s = 1,int e = TO){
	if(n == NULL)n = new node();
	if(s > at || e < at)return;
	if(s == e){
		n->val = val;
		return;
	}
	update_range(at , val , n->l , s , (s+e)/2);
	update_range(at , val , n->r , (s+e)/2+1 , e);
	n->marge();
}

ll get(int l,int r,node *&n,int s = 1,int e = TO){
	if(n == NULL)return 0;
	if(s > r || e < l || l > r)return 0LL;
	if(s >= l && e <= r)return n->val;
	ll a = get(l , r , n->l , s , (s+e) / 2);
	ll b = get(l , r , n->r , (s+e)/2+1 , e);
	return __gcd(a,b);
}

void update_range_2(int at,node *&n,node *&l , node*&r,int s = 1,int e = TO){
	if(n == NULL)n = new node();
	if(s > at || e < at)return;
	if(s == e){
		if(l == NULL)n->val = r->val;
		else if(r == NULL)n->val = l->val;
		else n->val = __gcd(l->val,r->val);
		return;
	}
	if(l == NULL){
		update_range_2(at , n->l,l,r->l , s , (s+e)/2);
		update_range_2(at , n->r,l,r->r , (s+e)/2+1 , e);	
	}else if(r == NULL){
		update_range_2(at , n->l,l->l,r , s , (s+e)/2);
		update_range_2(at , n->r,l->r,r , (s+e)/2+1 , e);
	}else{
		update_range_2(at , n->l,l->l,r->l , s , (s+e)/2);
		update_range_2(at , n->r,l->r,r->r , (s+e)/2+1 , e);
	}
	n->marge();
}

void update_range_2d(int at,ll val,node2d *&n = head2d,int s = 1,int e = TO){
	if(n == NULL)n = new node2d();
	if(s > at || e < at)return;
	if(s == e){
		update_range(p,val,n->child);
		return;
	}
	update_range_2d(at , val , n->l , s , (s+e)/2);
	update_range_2d(at , val , n->r , (s+e)/2+1 , e);
	update_range_2(p,n->child,n->l->child,n->r->child);
}

ll get_2d(int l,int r,node2d *& n = head2d,int s = 1,int e = TO){
	if(n == NULL)return 0;
	if(s > r || e < l || l > r)return 0LL;
	if(s >= l && e <= r){
		return get(p,q,n->child);
	}
	ll a = get_2d(l , r , n->l , s , (s+e) / 2);
	ll b = get_2d(l , r , n->r , (s+e)/2+1 , e);
	return __gcd(a,b);
}
 
void init(int R, int C) {
    head2d = new node2d();
}
 
void update(int P, int Q, long long K) {
	p = Q + 1;
	update_range_2d(P+1,K); 
}
 
long long calculate(int P, int Q, int U, int V) {
	p = Q + 1;q = V + 1;
	return get_2d(P+1,U+1);
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 7 ms 896 KB Output is correct
3 Correct 7 ms 896 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 7 ms 896 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 7 ms 896 KB Output is correct
10 Correct 6 ms 640 KB Output is correct
11 Correct 6 ms 512 KB Output is correct
12 Correct 5 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 384 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 1086 ms 78712 KB Output is correct
5 Correct 939 ms 78636 KB Output is correct
6 Correct 1118 ms 75896 KB Output is correct
7 Correct 1166 ms 75632 KB Output is correct
8 Correct 860 ms 47548 KB Output is correct
9 Correct 1131 ms 76280 KB Output is correct
10 Correct 1093 ms 75572 KB Output is correct
11 Correct 5 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 7 ms 896 KB Output is correct
3 Correct 9 ms 896 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 7 ms 896 KB Output is correct
7 Correct 6 ms 384 KB Output is correct
8 Correct 5 ms 512 KB Output is correct
9 Correct 8 ms 896 KB Output is correct
10 Correct 6 ms 640 KB Output is correct
11 Correct 6 ms 512 KB Output is correct
12 Correct 1550 ms 27664 KB Output is correct
13 Correct 1912 ms 13816 KB Output is correct
14 Correct 708 ms 2152 KB Output is correct
15 Correct 2241 ms 21480 KB Output is correct
16 Correct 758 ms 38216 KB Output is correct
17 Correct 1812 ms 26404 KB Output is correct
18 Correct 2868 ms 38648 KB Output is correct
19 Correct 2510 ms 38584 KB Output is correct
20 Correct 2257 ms 38136 KB Output is correct
21 Correct 5 ms 384 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 8 ms 896 KB Output is correct
3 Correct 8 ms 896 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 7 ms 896 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 7 ms 896 KB Output is correct
10 Correct 6 ms 640 KB Output is correct
11 Correct 6 ms 512 KB Output is correct
12 Correct 1261 ms 78524 KB Output is correct
13 Correct 881 ms 78544 KB Output is correct
14 Correct 1096 ms 76016 KB Output is correct
15 Correct 1386 ms 75836 KB Output is correct
16 Correct 821 ms 47480 KB Output is correct
17 Correct 1488 ms 76300 KB Output is correct
18 Correct 1216 ms 75672 KB Output is correct
19 Correct 1527 ms 27752 KB Output is correct
20 Correct 1932 ms 13944 KB Output is correct
21 Correct 701 ms 2164 KB Output is correct
22 Correct 2217 ms 21332 KB Output is correct
23 Correct 812 ms 38392 KB Output is correct
24 Correct 2183 ms 26488 KB Output is correct
25 Correct 3451 ms 38680 KB Output is correct
26 Correct 3028 ms 38816 KB Output is correct
27 Correct 2746 ms 38068 KB Output is correct
28 Runtime error 778 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Correct 7 ms 896 KB Output is correct
3 Correct 8 ms 896 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 7 ms 1024 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 7 ms 896 KB Output is correct
10 Correct 6 ms 640 KB Output is correct
11 Correct 6 ms 512 KB Output is correct
12 Correct 1056 ms 78072 KB Output is correct
13 Correct 916 ms 78072 KB Output is correct
14 Correct 1181 ms 75400 KB Output is correct
15 Correct 1178 ms 75256 KB Output is correct
16 Correct 762 ms 46840 KB Output is correct
17 Correct 1261 ms 75888 KB Output is correct
18 Correct 1085 ms 75000 KB Output is correct
19 Correct 1509 ms 27196 KB Output is correct
20 Correct 1882 ms 13276 KB Output is correct
21 Correct 708 ms 2040 KB Output is correct
22 Correct 2249 ms 20960 KB Output is correct
23 Correct 767 ms 37752 KB Output is correct
24 Correct 1931 ms 25988 KB Output is correct
25 Correct 3051 ms 38052 KB Output is correct
26 Correct 2368 ms 38264 KB Output is correct
27 Correct 2242 ms 37564 KB Output is correct
28 Runtime error 717 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -