oj.uz

Submission #238477

# Submission time Handle Problem Language Result Execution time Memory
238477 2020-06-11T13:49:52 Z figter001 Game (IOI13_game) C++17
63 / 100
 2827 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(l == NULL && r == NULL)return;
	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 8 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 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 6 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 7 ms 512 KB Output is correct
12 Correct 5 ms 512 KB Output is correct

Subtask #2
27.0 / 27.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 1101 ms 82260 KB Output is correct
5 Correct 928 ms 81692 KB Output is correct
6 Correct 1219 ms 79912 KB Output is correct
7 Correct 1166 ms 79564 KB Output is correct
8 Correct 823 ms 51084 KB Output is correct
9 Correct 1227 ms 80256 KB Output is correct
10 Correct 1125 ms 79368 KB Output is correct
11 Correct 6 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 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 768 KB Output is correct
11 Correct 6 ms 512 KB Output is correct
12 Correct 1520 ms 31092 KB Output is correct
13 Correct 1914 ms 17272 KB Output is correct
14 Correct 710 ms 6240 KB Output is correct
15 Correct 2191 ms 24936 KB Output is correct
16 Correct 768 ms 41688 KB Output is correct
17 Correct 1744 ms 30776 KB Output is correct
18 Correct 2661 ms 43084 KB Output is correct
19 Correct 2348 ms 43320 KB Output is correct
20 Correct 2322 ms 42668 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 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 768 KB Output is correct
11 Correct 6 ms 512 KB Output is correct
12 Correct 1065 ms 82124 KB Output is correct
13 Correct 880 ms 81912 KB Output is correct
14 Correct 1089 ms 79692 KB Output is correct
15 Correct 1159 ms 79500 KB Output is correct
16 Correct 766 ms 51064 KB Output is correct
17 Correct 1138 ms 80204 KB Output is correct
18 Correct 1086 ms 79476 KB Output is correct
19 Correct 1507 ms 31120 KB Output is correct
20 Correct 1872 ms 17016 KB Output is correct
21 Correct 697 ms 6136 KB Output is correct
22 Correct 2218 ms 25152 KB Output is correct
23 Correct 771 ms 41588 KB Output is correct
24 Correct 1678 ms 30492 KB Output is correct
25 Correct 2827 ms 43180 KB Output is correct
26 Correct 2289 ms 43516 KB Output is correct
27 Correct 2133 ms 42496 KB Output is correct
28 Runtime error 691 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 6 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 4 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 1125 ms 82308 KB Output is correct
13 Correct 960 ms 81964 KB Output is correct
14 Correct 1125 ms 79808 KB Output is correct
15 Correct 1269 ms 79608 KB Output is correct
16 Correct 807 ms 50916 KB Output is correct
17 Correct 1232 ms 80276 KB Output is correct
18 Correct 1084 ms 79480 KB Output is correct
19 Correct 1562 ms 31100 KB Output is correct
20 Correct 1930 ms 17016 KB Output is correct
21 Correct 704 ms 6264 KB Output is correct
22 Correct 2192 ms 25208 KB Output is correct
23 Correct 803 ms 41604 KB Output is correct
24 Correct 1705 ms 30860 KB Output is correct
25 Correct 2796 ms 42984 KB Output is correct
26 Correct 2398 ms 43288 KB Output is correct
27 Correct 2494 ms 42860 KB Output is correct
28 Runtime error 689 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -