oj.uz

Submission #238488

# Submission time Handle Problem Language Result Execution time Memory
238488 2020-06-11T14:26:21 Z figter001 Game (IOI13_game) C++17
63 / 100
 1904 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;
	ll val;
	node2d(){
		l = r = NULL;
		val = 0;
		child = new node();
	}
	void marge(){
		val = __gcd(l->val , r->val);
	}
};

node2d *head2d;

void update_range(int at,ll val,node *&n,int s = 1,int e = c){
	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 = c){
	if(n == NULL)return 0;
	if(n->val == 0)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(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;
	}
	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);
		n->val = n->child->val;
		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);
	n->marge();
}

ll get_2d(int l,int r,node2d *& n = head2d,int s = 1,int e = ::r){
	if(n == NULL)return 0;
	if(n->val == 0)return 0;
	if(s > r || e < l || l > r)return 0;
	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 512 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 6 ms 544 KB Output is correct
7 Correct 5 ms 128 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 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 5 ms 256 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 4 ms 256 KB Output is correct
4 Correct 624 ms 18276 KB Output is correct
5 Correct 443 ms 18796 KB Output is correct
6 Correct 604 ms 15804 KB Output is correct
7 Correct 628 ms 15480 KB Output is correct
8 Correct 412 ms 10228 KB Output is correct
9 Correct 634 ms 15736 KB Output is correct
10 Correct 616 ms 15072 KB Output is correct
11 Correct 4 ms 256 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 512 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 6 ms 512 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 1000 ms 22648 KB Output is correct
13 Correct 1491 ms 8952 KB Output is correct
14 Correct 339 ms 1144 KB Output is correct
15 Correct 1793 ms 13452 KB Output is correct
16 Correct 269 ms 29724 KB Output is correct
17 Correct 1022 ms 18424 KB Output is correct
18 Correct 1760 ms 29944 KB Output is correct
19 Correct 1599 ms 30200 KB Output is correct
20 Correct 1405 ms 29432 KB Output is correct
21 Correct 4 ms 256 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 256 KB Output is correct
2 Correct 5 ms 512 KB Output is correct
3 Correct 5 ms 560 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 512 KB Output is correct
7 Correct 5 ms 384 KB Output is correct
8 Correct 4 ms 384 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 635 ms 18320 KB Output is correct
13 Correct 468 ms 18808 KB Output is correct
14 Correct 549 ms 15992 KB Output is correct
15 Correct 687 ms 15456 KB Output is correct
16 Correct 474 ms 10232 KB Output is correct
17 Correct 792 ms 15608 KB Output is correct
18 Correct 558 ms 15096 KB Output is correct
19 Correct 980 ms 22776 KB Output is correct
20 Correct 1474 ms 8824 KB Output is correct
21 Correct 339 ms 1144 KB Output is correct
22 Correct 1787 ms 13184 KB Output is correct
23 Correct 303 ms 29560 KB Output is correct
24 Correct 1004 ms 18424 KB Output is correct
25 Correct 1753 ms 29944 KB Output is correct
26 Correct 1524 ms 30152 KB Output is correct
27 Correct 1409 ms 29416 KB Output is correct
28 Runtime error 706 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 4 ms 384 KB Output is correct
2 Correct 5 ms 512 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 512 KB Output is correct
7 Correct 5 ms 256 KB Output is correct
8 Correct 5 ms 384 KB Output is correct
9 Correct 5 ms 512 KB Output is correct
10 Correct 5 ms 384 KB Output is correct
11 Correct 5 ms 384 KB Output is correct
12 Correct 627 ms 18424 KB Output is correct
13 Correct 455 ms 18808 KB Output is correct
14 Correct 545 ms 15864 KB Output is correct
15 Correct 636 ms 15608 KB Output is correct
16 Correct 424 ms 10224 KB Output is correct
17 Correct 666 ms 15724 KB Output is correct
18 Correct 558 ms 15352 KB Output is correct
19 Correct 971 ms 22776 KB Output is correct
20 Correct 1483 ms 9132 KB Output is correct
21 Correct 339 ms 1016 KB Output is correct
22 Correct 1831 ms 13176 KB Output is correct
23 Correct 306 ms 29688 KB Output is correct
24 Correct 1030 ms 18424 KB Output is correct
25 Correct 1904 ms 29944 KB Output is correct
26 Correct 1466 ms 30072 KB Output is correct
27 Correct 1408 ms 29752 KB Output is correct
28 Runtime error 638 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -