oj.uz

Submission #127559

# Submission time Handle Problem Language Result Execution time Memory
127559 2019-07-09T14:59:00 Z MoNsTeR_CuBe Game (IOI13_game) C++17
37 / 100
 13000 ms 71608 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
#define int long long
struct node{
	node* l, *r;
	int val;
};

void Build(node *root, int left, int right){
	if(left == right){
		return;
	}
	root->l = new node{NULL,NULL,0};
	root->r = new node{NULL,NULL,0};
	int mid = (left+right)/2;
	Build(root->l, left, mid);
	Build(root->r, mid+1, right);
}

int Update(node *root, int left, int right, int qL, int qR, int val){
	if(left > qR || right < qL) return root->val;
	if(left >= qL && right <= qR){
		root->val = val;
		return val;
	}
	int mid = (left+right)/2;
	
	return root->val = gcd2(Update(root->l, left, mid, qL, qR, val), Update(root->r, mid+1, right, qL, qR, val));
}

int query(node *root, int left, int right, int qL, int qR){
	if(left > qR || right < qL){
		return 0;
	}
	if(left >= qL && right <= qR){
		return root->val;
	}
	int mid = (left+right)/2;
	return gcd2(query(root->l, left, mid, qL, qR), query(root->r, mid+1, right, qL, qR));
}

vector< node* > roots;

int r, c;

#undef int

void init(int R, int C) {
    #define int long long
    r = R, c = C;
    roots.resize(R+1);
    for(int i = 1; i <= R; i++){
		roots[i] = new node{NULL,NULL,0};
		Build(roots[i], 1, C);
	}
	#undef int
}

void update(int P, int Q, long long K) {
    #define int long long 
    Update(roots[P+1], 1, c, Q+1, Q+1, K);
    #undef int
}

long long calculate(int P, int Q, int U, int V) {
	#define int long long 
    int gcd = 0;
    for(int i = P+1; i <= U+1; i++){
		gcd = gcd2(gcd, query(roots[i], 1, c, Q+1, V+1));
	}
    return gcd;
    #undef int
}

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 2 ms 376 KB Output is correct
2 Correct 4 ms 1016 KB Output is correct
3 Correct 3 ms 888 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 892 KB Output is correct
6 Correct 3 ms 888 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 3 ms 1016 KB Output is correct
10 Correct 4 ms 1016 KB Output is correct
11 Correct 3 ms 1016 KB Output is correct
12 Correct 2 ms 376 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2273 ms 71576 KB Output is correct
5 Correct 879 ms 71488 KB Output is correct
6 Correct 1937 ms 68856 KB Output is correct
7 Correct 1985 ms 68600 KB Output is correct
8 Correct 1666 ms 68856 KB Output is correct
9 Correct 1915 ms 68600 KB Output is correct
10 Correct 1778 ms 68216 KB Output is correct
11 Correct 2 ms 376 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 KB Output is correct
2 Correct 4 ms 1016 KB Output is correct
3 Correct 4 ms 1016 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 4 ms 1016 KB Output is correct
6 Correct 3 ms 876 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 4 ms 1016 KB Output is correct
10 Correct 3 ms 1016 KB Output is correct
11 Correct 3 ms 892 KB Output is correct
12 Execution timed out 13081 ms 64048 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 1016 KB Output is correct
3 Correct 4 ms 888 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 888 KB Output is correct
6 Correct 3 ms 888 KB Output is correct
7 Correct 2 ms 376 KB Output is correct
8 Correct 2 ms 504 KB Output is correct
9 Correct 3 ms 1016 KB Output is correct
10 Correct 3 ms 1016 KB Output is correct
11 Correct 3 ms 1016 KB Output is correct
12 Correct 2099 ms 71608 KB Output is correct
13 Correct 874 ms 71344 KB Output is correct
14 Correct 1910 ms 68856 KB Output is correct
15 Correct 2175 ms 68508 KB Output is correct
16 Correct 1644 ms 68984 KB Output is correct
17 Correct 2021 ms 68472 KB Output is correct
18 Correct 1844 ms 68176 KB Output is correct
19 Execution timed out 13024 ms 64108 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 4 ms 1016 KB Output is correct
3 Correct 4 ms 1016 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 3 ms 888 KB Output is correct
6 Correct 4 ms 888 KB Output is correct
7 Correct 2 ms 504 KB Output is correct
8 Correct 3 ms 508 KB Output is correct
9 Correct 4 ms 888 KB Output is correct
10 Correct 3 ms 1016 KB Output is correct
11 Correct 3 ms 888 KB Output is correct
12 Correct 2227 ms 71428 KB Output is correct
13 Correct 878 ms 71288 KB Output is correct
14 Correct 1965 ms 68856 KB Output is correct
15 Correct 2045 ms 68568 KB Output is correct
16 Correct 1909 ms 68888 KB Output is correct
17 Correct 1951 ms 68728 KB Output is correct
18 Correct 1881 ms 68216 KB Output is correct
19 Execution timed out 13030 ms 64084 KB Time limit exceeded
20 Halted 0 ms 0 KB -