Submission #167481

# Submission time Handle Problem Language Result Execution time Memory
167481 2019-12-08T16:29:51 Z cgiosy Game (IOI13_game) C++17
0 / 100
3 ms 396 KB
#include <bits/stdc++.h>
using namespace std;
#include "game.h"
using ll=long long;

struct T { ll x; int l, r; };
vector<T> X;
struct seg {
	int N, root;
	seg(const int n) : N(n-1) { root=-1; }
	ll get(int l, int r, int s, int e, int i) const {
		if(i==-1 || e<l || r<s) return 0;
		if(l<=s && e<=r) return X[i].x;
		int m=(s+e)>>1;
		return gcd(get(l, r, s, m, X[i].l), get(l, r, m+1, e, X[i].r));
	}
	ll get(int l, int r) const { return get(l, r, 0, N, root); }
	ll set(int p, ll x, int s, int e, int&i) {
		if(p<s || e<p) return ~i ? X[i].x : 0;
		if(i==-1) {
			i=X.size();
			X.push_back({0, -1, -1});
		}
		if(s==e) return X[i].x=x;
		int m=(s+e)>>1;
		return X[i].x=gcd(set(p, x, s, m, X[i].l), set(p, x, m+1, e, X[i].r));
	}
	void set(int p, ll x) { set(p, x, 0, N, root); }
};

struct T2 { seg x; int l, r; };
vector<T2> Y;
struct seg2 {
	int N, M, root;
	seg2(int n, int m) : N(n-1), M(m) { root=-1; }
	ll get(int l1, int r1, int l2, int r2, int s, int e, int i) const {
		if(i==-1 || e<l1 || r1<s) return 0;
		if(l1<=s && e<=r1) return Y[i].x.get(l2, r2);
		int m=(s+e)>>1;
		return gcd(get(l1, r1, l2, r2, s, m, Y[i].l), get(l1, r1, l2, r2, m+1, e, Y[i].r));
	}
	ll get(int l1, int r1, int l2, int r2) const { return get(l1, r1, l2, r2, 0, N, root); }
	void set(int p, int q, ll x, int s, int e, int&i) {
		if(p<s || e<p) return;
		if(i==-1) {
			i=Y.size();
			Y.push_back({seg(M), -1, -1});
		}
		Y[i].x.set(q, x);
		if(s==e) return;
		int m=(s+e)>>1;
		set(p, q, x, s, m, Y[i].l), set(p, q, x, m+1, e, Y[i].r);
	}
	void set(int p, int q, ll x) { set(p, q, x, 0, N, root); }
} *T;

void init(int R, int C) {
	T=new seg2(R, C);
	X.reserve(1<<24);
	Y.reserve(1<<20);
}

void update(int P, int Q, ll K) {
	T->set(P, Q, K);
}

ll calculate(int P, int Q, int U, int V) {
	return T->get(P, U, Q, 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;
      ^~~
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 3 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 2 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 3 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2 ms 396 KB Output is correct
2 Incorrect 3 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Incorrect 3 ms 376 KB Output isn't correct
3 Halted 0 ms 0 KB -