oj.uz

답안 #330357

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
330357 2020-11-24T22:22:24 Z arwaeystoamneg 게임 (IOI13_game) C++17
0 / 100
 1012 ms 51692 KB 
#include "game.h"
#include<bits/stdc++.h>
#include<unordered_set>
#include<unordered_map>
#include<chrono>

using namespace std;
typedef pair<int, int> pii;
typedef long long ll;
typedef pair<ll, ll> pll;
// warning: ld is rougly 2x slower than double. Proof: ld: https://oj.uz/submission/319677 double: https://oj.uz/submission/319678
typedef long double ld;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pair<int, int>> vpi;
typedef vector<pair<ll, ll>> vpll;

#define FOR(i,a,b) for (int i = (a); i < (b); ++i)
#define F0R(i,a) FOR(i,0,a)
#define ROF(i,a,b) for (int i = (b)-1; i >= (a); --i)
#define R0F(i,a) ROF(i,0,a)
#define trav(a,x) for (auto& a: x)

#define pb push_back
#define mp make_pair
#define rsz resize
#define sz(x) int(x.size())
#define all(x) x.begin(),x.end()
#define f first
#define s second
#define endl '\n'
#define test int testc;cin>>testc;while(testc--)
const int dx[4] = { 1,0,-1,0 }, dy[4] = { 0,1,0,-1 }; // for every grid problem!!
const ll linf = 4000000000000000000LL;
const ll inf = 1000000007;//998244353
const ld pi = 3.1415926535;

void pv(vi a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vll a) { trav(x, a)cout << x << " "; cout << endl; }void pv(vector<vi>a) {
	F0R(i, sz(a)) { cout << i << endl; pv(a[i]); cout << endl; }
}void pv(vector<vll>a) { F0R(i, sz(a)) { cout << i << endl; pv(a[i]); }cout << endl; }void pv(vector<string>a) { trav(x, a)cout << x << endl; cout << endl; }

ll gcd(ll a, ll b)
{
	if (a > b)swap(a, b);
	if (a == 0)return b;
	return gcd(a, b % a);
}

class sum_range_tree
{
	struct node
	{
		ll val;
		struct node* C[2];
		node()
		{
			val = 0;
			C[0] = NULL;
			C[1] = NULL;
		}
		node* getc(int c)
		{
			if (C[c] == NULL)
			{
				C[c] = new node;
			}
			return C[c];
		}
		void update(int i, ll v, int l, int r)
		{
			if (l == r)
			{
				val = v;
				return;
			}
			int mid = (l + r) / 2;
			if (i <= mid)
				getc(0)->update(i, v, l, mid);
			else
				getc(1)->update(i, v, mid + 1, r);
			val = gcd(C[0] ? C[0]->val : 0, C[1] ? C[1]->val : 0);
		}
		ll query(int l, int r, int tl, int tr)
		{
			if (tl >= l && tr <= r)
				return val;
			else if (tl > r || l > tr)
				return 0;
			int mid = (tl + tr) / 2;
			return gcd((C[0] ? C[0]->query(l, r, tl, mid) : 0), (C[1] ? C[1]->query(l, r, mid + 1, tr) : 0));
		}
	};
	node* top;
public:void build()
{
	top = new node;
}
public:void update(int i, ll v)
{
	top->update(i, v, 0, inf);
}
public:ll query(int l, int r)
{
	return top->query(l, r, 0, inf);
}
};
class sum_range_tree_2D
{
	struct node
	{
		sum_range_tree st;
		struct node* C[2];
		node()
		{
			st.build();
			C[0] = NULL;
			C[1] = NULL;
		}
		node* getc(int c)
		{
			if (C[c] == NULL)
			{
				C[c] = new node;
			}
			return C[c];
		}
		void update(int x1, int x2, int x, int y, ll val)
		{
			if (x<x1 || x>x2)
				return;
			if (x1 == x2)
			{
				st.update(y, val);
				return;
			}
			int mid = (x1 + x2) / 2;
			if (x <= mid)
			{
				getc(0)->update(x1, mid, x, y, val);
				st.update(y, gcd(val, C[1] ? C[1]->st.query(y, y) : 0));
			}
			else if (x > mid)
			{
				getc(1)->update(mid + 1, x2, x, y, val);
				st.update(y, gcd(val, C[0] ? C[0]->st.query(y, y) : 0));
			}
		}
		ll query(int x1, int x2, int qx1, int qx2, int qy1, int qy2)
		{
			if (x2<qx1 || x1>qx2)
			{
				return 0;
			}
			if (x1 >= qx1 && x2 <= qx2)
			{
				return st.query(qy1, qy2);
			}
			int mid = (x1 + x2) / 2;
			return gcd(C[0] ? C[0]->query(x1, mid, qx1, qx2, qy1, qy2) : 0, C[1] ? C[1]->query(mid + 1, x2, qx1, qx2, qy1, qy2) : 0);
		}
	};
	node* top;
public:void build()
{
	top = new node;
}
public:void update(int x, int y, ll val)
{
	top->update(0, inf, x, y, val);
}
public:ll query(int x1, int y1, int x2, int y2)
{
	return top->query(0, inf, x1, x2, y1, y2);
}
};
sum_range_tree_2D sum;
void init(int r, int c)
{
	sum.build();
}
void update(int p, int q, ll k)
{
	sum.update(p, q, k);
}
ll calculate(int p, int q, int u, int v)
{
	return sum.query(p, q, u, v);
}

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 3 ms 640 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 996 ms 51488 KB Output is correct
5 Correct 821 ms 51692 KB Output is correct
6 Incorrect 1012 ms 48492 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Incorrect 3 ms 620 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 376 KB Output is correct
2 Incorrect 3 ms 620 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 3 ms 620 KB Output isn't correct
3 Halted 0 ms 0 KB -