oj.uz

Submission #238485

# Submission time Handle Problem Language Result Execution time Memory
238485 2020-06-11T14:10:06 Z figter001 Game (IOI13_game) C++17
63 / 100
 1824 ms 256000 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 = 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(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;
	}
	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 = ::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 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 5 ms 512 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 512 KB Output is correct
10 Correct 5 ms 436 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 5 ms 256 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Correct 661 ms 18544 KB Output is correct
5 Correct 445 ms 18680 KB Output is correct
6 Correct 561 ms 15736 KB Output is correct
7 Correct 628 ms 15564 KB Output is correct
8 Correct 427 ms 10136 KB Output is correct
9 Correct 611 ms 15608 KB Output is correct
10 Correct 606 ms 15096 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 4 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 5 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 986 ms 22880 KB Output is correct
13 Correct 1453 ms 8800 KB Output is correct
14 Correct 359 ms 1148 KB Output is correct
15 Correct 1725 ms 13004 KB Output is correct
16 Correct 264 ms 29560 KB Output is correct
17 Correct 1010 ms 18388 KB Output is correct
18 Correct 1739 ms 29944 KB Output is correct
19 Correct 1525 ms 30336 KB Output is correct
20 Correct 1438 ms 29344 KB Output is correct
21 Correct 5 ms 256 KB Output is correct

Subtask #4
0 / 17.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 4 ms 256 KB Output is correct
6 Correct 5 ms 512 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 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 632 ms 18428 KB Output is correct
13 Correct 451 ms 18680 KB Output is correct
14 Correct 557 ms 15840 KB Output is correct
15 Correct 627 ms 15480 KB Output is correct
16 Correct 419 ms 10104 KB Output is correct
17 Correct 611 ms 15736 KB Output is correct
18 Correct 573 ms 15224 KB Output is correct
19 Correct 966 ms 22776 KB Output is correct
20 Correct 1419 ms 8824 KB Output is correct
21 Correct 366 ms 1144 KB Output is correct
22 Correct 1744 ms 13328 KB Output is correct
23 Correct 268 ms 29560 KB Output is correct
24 Correct 1002 ms 18424 KB Output is correct
25 Correct 1744 ms 29944 KB Output is correct
26 Correct 1471 ms 30232 KB Output is correct
27 Correct 1494 ms 29480 KB Output is correct
28 Runtime error 748 ms 256000 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 256 KB Output is correct
2 Correct 5 ms 544 KB Output is correct
3 Correct 5 ms 512 KB Output is correct
4 Correct 4 ms 384 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 256 KB Output is correct
9 Correct 6 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 659 ms 18408 KB Output is correct
13 Correct 465 ms 18680 KB Output is correct
14 Correct 562 ms 15864 KB Output is correct
15 Correct 669 ms 15456 KB Output is correct
16 Correct 420 ms 10104 KB Output is correct
17 Correct 622 ms 15736 KB Output is correct
18 Correct 565 ms 15224 KB Output is correct
19 Correct 967 ms 22520 KB Output is correct
20 Correct 1444 ms 8736 KB Output is correct
21 Correct 375 ms 1144 KB Output is correct
22 Correct 1736 ms 13052 KB Output is correct
23 Correct 261 ms 29560 KB Output is correct
24 Correct 1062 ms 18424 KB Output is correct
25 Correct 1824 ms 29816 KB Output is correct
26 Correct 1502 ms 30204 KB Output is correct
27 Correct 1391 ms 29448 KB Output is correct
28 Runtime error 684 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -