oj.uz

Submission #414546

# Submission time Handle Problem Language Result Execution time Memory
414546 2021-05-30T15:58:04 Z ritul_kr_singh Game (IOI13_game) C++17
0 / 100
 11 ms 604 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define sp << ' ' <<
#define nl << '\n'
#include "game.h"

const int sz = 1<<30; 

struct SparseSegmentTree{
	vector<ll> a = {0}; vector<int> c = {-1};
	int curr = 0, i, l, r; ll v;
	void update(int x, int lx, int rx){
		if(rx-lx == 1) return void(a[x] = v);
		if(c[x] < 0){
			c[x] = curr, curr += 2;
			c.push_back(-1), c.push_back(-1);
			a.resize(a.size() + 2);
		}
		int mx = (lx + rx) / 2;
		if(i < mx) update(c[x]+1, lx, mx);
		else update(c[x]+2, mx, rx);
		a[x] = gcd(a[c[x]+1], a[c[x]+2]);
	}
	void update(int _i, ll _v){ i = _i, v = _v, update(0, 0, sz); }
	ll rangeGcd(int x, int lx, int rx){
		if(r<=lx || rx<=l) return 0;
		if(l<=lx && rx<=r) return a[x];
		if(c[x] < 0) return 0;
		int mx = (lx + rx) / 2;
		return gcd(rangeGcd(c[x]+1, lx, mx), rangeGcd(c[x]+2, mx, rx));
	}
	ll rangeGcd(int _l, int _r){ return l = _l, r = _r + 1, rangeGcd(0, 0, sz); }
};

vector<SparseSegmentTree> a(1); vector<int> c = {-1};
int curr = 0, l, r, ly, ry; ll v;
ll calculate(int P, int Q, int U, int V);

void upd(int x, int lx, int rx){
	if(rx-lx == 1) return a[x].update(ly, v);
	if(c[x] < 0){
		c[x] = curr, curr += 2;
		c.push_back(-1), c.push_back(-1);
		a.resize(a.size() + 2);
	}
	int mx = (lx + rx) / 2;
	if(l < mx) upd(c[x]+1, lx, mx);
	else upd(c[x]+2, mx, rx);
	a[x].update(ly, gcd(v, gcd(calculate(lx, ly, l - 1, ly), calculate(l + 1, ly, rx - 1, ly))));
}

ll get(int x, int lx, int rx){
	if(r<=lx || rx<=l) return 0;
	if(l<=lx && rx<=r) return a[x].rangeGcd(ly, ry);
	if(c[x] < 0) return 0;
	int mx = (lx + rx) / 2;
	return gcd(get(c[x]+1, lx, mx), get(c[x]+2, mx, rx));
}

void init(int R, int C){}
void update(int P, int Q, ll K){
	l = P, ly = Q, v = K;
	upd(0, 0, sz);
}
ll calculate(int P, int Q, int U, int V){
	l = P, r = U + 1, ly = Q, ry = V;
	return get(0, 0, sz);
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 10 ms 604 KB Output is correct
3 Correct 10 ms 588 KB Output is correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

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

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 204 KB Output is correct
2 Correct 10 ms 548 KB Output is correct
3 Correct 11 ms 588 KB Output is correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 10 ms 544 KB Output is correct
3 Correct 9 ms 604 KB Output is correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 332 KB Output is correct
2 Correct 10 ms 520 KB Output is correct
3 Correct 10 ms 588 KB Output is correct
4 Incorrect 1 ms 332 KB Output isn't correct
5 Halted 0 ms 0 KB -