oj.uz

Submission #238528

# Submission time Handle Problem Language Result Execution time Memory
238528 2020-06-11T16:14:38 Z figter001 Game (IOI13_game) C++17
63 / 100
 1807 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(){
		if(l == NULL && r == NULL)return;
		else if(l == NULL)val = r->val;
		else if(r == NULL)val = l->val;
		else 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 = c){
	if(s > at || e < at)return;
	if(n == NULL)n = new node();
	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 = c){
	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 = c){
	if(s > at || e < at)return;	
	if(n == NULL)n = new node();
	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;
	}
	int md = (s+e)/2;
	if(l == NULL){
		update_range_2(at , n->l,l,r->l , s , md);
		update_range_2(at , n->r,l,r->r , md+1 , e);	
	}else if(r == NULL){
		update_range_2(at , n->l,l->l,r , s , md);
		update_range_2(at , n->r,l->r,r , md+1 , e);
	}else{
		update_range_2(at , n->l,l->l,r->l , s , md);
		update_range_2(at , n->r,l->r,r->r , md+1 , e);
	}
	n->marge();
}

void update_range_2d(int at,ll val,node2d *&n = head2d,int s = 1,int e = ::r){
	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 = ::r){
	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) {
	r = R;
	c = 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 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 5 ms 384 KB Output is correct
5 Correct 5 ms 384 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 5 ms 256 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 4 ms 256 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 4 ms 256 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 597 ms 12728 KB Output is correct
5 Correct 430 ms 13004 KB Output is correct
6 Correct 500 ms 9848 KB Output is correct
7 Correct 563 ms 9848 KB Output is correct
8 Correct 410 ms 6716 KB Output is correct
9 Correct 593 ms 9816 KB Output is correct
10 Correct 501 ms 9464 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 4 ms 256 KB Output is correct
2 Correct 5 ms 384 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 5 ms 256 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 941 ms 15864 KB Output is correct
13 Correct 1458 ms 6332 KB Output is correct
14 Correct 338 ms 1072 KB Output is correct
15 Correct 1807 ms 9104 KB Output is correct
16 Correct 237 ms 18376 KB Output is correct
17 Correct 868 ms 11536 KB Output is correct
18 Correct 1687 ms 18696 KB Output is correct
19 Correct 1252 ms 19088 KB Output is correct
20 Correct 1255 ms 18296 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 5 ms 512 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 4 ms 256 KB Output is correct
5 Correct 4 ms 256 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 4 ms 256 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 588 ms 12620 KB Output is correct
13 Correct 431 ms 13048 KB Output is correct
14 Correct 507 ms 10068 KB Output is correct
15 Correct 602 ms 9720 KB Output is correct
16 Correct 403 ms 6776 KB Output is correct
17 Correct 548 ms 9976 KB Output is correct
18 Correct 560 ms 9336 KB Output is correct
19 Correct 938 ms 15992 KB Output is correct
20 Correct 1447 ms 6364 KB Output is correct
21 Correct 332 ms 1016 KB Output is correct
22 Correct 1776 ms 8952 KB Output is correct
23 Correct 232 ms 18296 KB Output is correct
24 Correct 846 ms 11640 KB Output is correct
25 Correct 1430 ms 18680 KB Output is correct
26 Correct 1332 ms 18936 KB Output is correct
27 Correct 1313 ms 18296 KB Output is correct
28 Runtime error 1071 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 5 ms 384 KB Output is correct
3 Correct 5 ms 384 KB Output is correct
4 Correct 5 ms 256 KB Output is correct
5 Correct 5 ms 256 KB Output is correct
6 Correct 5 ms 384 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 384 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 592 ms 12920 KB Output is correct
13 Correct 438 ms 13304 KB Output is correct
14 Correct 503 ms 10220 KB Output is correct
15 Correct 558 ms 9976 KB Output is correct
16 Correct 388 ms 6904 KB Output is correct
17 Correct 709 ms 10104 KB Output is correct
18 Correct 533 ms 9656 KB Output is correct
19 Correct 970 ms 16248 KB Output is correct
20 Correct 1453 ms 6604 KB Output is correct
21 Correct 344 ms 1400 KB Output is correct
22 Correct 1764 ms 9048 KB Output is correct
23 Correct 261 ms 18556 KB Output is correct
24 Correct 860 ms 12024 KB Output is correct
25 Correct 1679 ms 19116 KB Output is correct
26 Correct 1425 ms 19192 KB Output is correct
27 Correct 1199 ms 18552 KB Output is correct
28 Runtime error 1089 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -