oj.uz

Submission #49956

# Submission time Handle Problem Language Result Execution time Memory
49956 2018-06-05T10:29:35 Z RezwanArefin01 Game (IOI13_game) C++11
0 / 100
 4 ms 1252 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std; 

typedef long long ll; 

ll gcd(ll X, ll Y) {
    ll tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

int N, M; 

struct node1D {
	ll g; 
	node1D *L, *R; 
	node1D() {
		L = R = NULL; 
		g = 0; 
	}
	void update(int l, int r, int x, ll k) {
		if(l == r) { g = k; return; }
		int m = l + r >> 1; 
		if(x <= m) {
			if(!L) L = new node1D(); 
			L -> update(l, m, x, k); 
		} else {
			if(!R) R = new node1D(); 
			R -> update(m + 1, r, x, k); 
		}
		if(L && R) g = gcd(L -> g, R -> g);
		else if(L) g = L -> g; 
		else g = R -> g; 
	}
	ll get(int l, int r, int i, int j) {
		if(r < i || l > j) return 0; 
		if(i <= l && r <= j) return g; 
		int m = l + r >> 1; 
		if(L && R) {
			return gcd(L -> get(l, m, i, j), R -> get(m + 1, r, i, j));
		} else if(L) return L -> get(l, m, i, j); 
		else if(R) return R -> get(m + 1, r, i, j);
		else return 0; 
	}
};

struct node2D {
	node1D *t; 
	node2D *L, *R; 
	node2D() {
		t = new node1D(); 
		L = R = NULL; 
	}
	void update(int l, int r, int x, int y, ll K) {
		t -> update(0, M - 1, y, K);
		if(l == r) return;  
		int m = l + r >> 1; 
		if(x <= m) {
			if(!L) L = new node2D();
			L -> update(l, m, x, y, K);
		} else {
			if(!R) R = new node2D(); 
			R -> update(m + 1, r, x, y, K);
		}
	}
	ll get(int l, int r, int x1, int y1, int x2, int y2) {
		if(r < x1 || l > x2) return 0; 
		if(x1 <= l && r <= x2) 
			return t -> get(0, M - 1, y1, y2);
		int m = l + r >> 1; 
		if(L && R) {
			return gcd(L -> get(l, m, x1, y1, x2, y2), R -> get(m + 1, r, x1, y1, x2, y2));
		} else if(L) return L -> get(l, m, x1, y1, x2, y2); 
		else if(R) return R -> get(m + 1, r, x1, y1, x2, y2); 
		else return 0;
	}
} *root;

void init(int R, int C) {
    N = R, M = C; 
    root = new node2D(); 
}

void update(int P, int Q, ll K) {
    root -> update(0, N - 1, P, Q, K); 
}

ll calculate(int P, int Q, int U, int V) {
    return root -> get(0, N - 1, P, Q, U, V);
}

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;
      ^~~
game.cpp: In member function 'void node1D::update(int, int, int, ll)':
game.cpp:28:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = l + r >> 1; 
           ~~^~~
game.cpp: In member function 'll node1D::get(int, int, int, int)':
game.cpp:43:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = l + r >> 1; 
           ~~^~~
game.cpp: In member function 'void node2D::update(int, int, int, int, ll)':
game.cpp:62:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = l + r >> 1; 
           ~~^~~
game.cpp: In member function 'll node2D::get(int, int, int, int, int, int)':
game.cpp:75:13: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   int m = l + r >> 1; 
           ~~^~~

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 504 KB Output is correct
2 Incorrect 3 ms 628 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 696 KB Output is correct
2 Incorrect 2 ms 756 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1004 KB Output is correct
2 Incorrect 3 ms 1196 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1196 KB Output is correct
2 Incorrect 2 ms 1244 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1244 KB Output is correct
2 Incorrect 3 ms 1252 KB Output isn't correct
3 Halted 0 ms 0 KB -