Submission #330359

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
330359	2020-11-24T22:26:11 Z	arwaeystoamneg	Game (IOI13_game)	C++17	63 / 100	2606 ms	256004 KB

game

#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(C[0]->st.query(y, y), 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(C[0] ? C[0]->st.query(y, y) : 0, C[1]->st.query(y, y)));
			}
		}
		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

10.0 / 10.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	2 ms	364 KB	Output is correct
2	Correct	3 ms	620 KB	Output is correct
3	Correct	3 ms	620 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	3 ms	748 KB	Output is correct
7	Correct	1 ms	384 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	3 ms	620 KB	Output is correct
10	Correct	2 ms	492 KB	Output is correct
11	Correct	2 ms	492 KB	Output is correct
12	Correct	1 ms	364 KB	Output is correct

Subtask #2

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	376 KB	Output is correct
2	Correct	1 ms	364 KB	Output is correct
3	Correct	1 ms	364 KB	Output is correct
4	Correct	1073 ms	50668 KB	Output is correct
5	Correct	911 ms	50540 KB	Output is correct
6	Correct	1113 ms	48620 KB	Output is correct
7	Correct	1146 ms	48904 KB	Output is correct
8	Correct	754 ms	30828 KB	Output is correct
9	Correct	1174 ms	49132 KB	Output is correct
10	Correct	1150 ms	48620 KB	Output is correct
11	Correct	1 ms	364 KB	Output is correct

Subtask #3

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	3 ms	620 KB	Output is correct
3	Correct	3 ms	620 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	3 ms	748 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	3 ms	620 KB	Output is correct
10	Correct	2 ms	492 KB	Output is correct
11	Correct	2 ms	492 KB	Output is correct
12	Correct	1527 ms	20844 KB	Output is correct
13	Correct	1903 ms	11176 KB	Output is correct
14	Correct	665 ms	3052 KB	Output is correct
15	Correct	2182 ms	15216 KB	Output is correct
16	Correct	747 ms	25580 KB	Output is correct
17	Correct	1621 ms	18156 KB	Output is correct
18	Correct	2576 ms	25836 KB	Output is correct
19	Correct	2278 ms	25872 KB	Output is correct
20	Correct	2168 ms	25324 KB	Output is correct
21	Correct	1 ms	492 KB	Output is correct

Subtask #4

0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	3 ms	620 KB	Output is correct
3	Correct	3 ms	620 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	3 ms	620 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	3 ms	620 KB	Output is correct
10	Correct	2 ms	492 KB	Output is correct
11	Correct	2 ms	492 KB	Output is correct
12	Correct	1078 ms	52332 KB	Output is correct
13	Correct	900 ms	52972 KB	Output is correct
14	Correct	1120 ms	49644 KB	Output is correct
15	Correct	1144 ms	49132 KB	Output is correct
16	Correct	762 ms	31220 KB	Output is correct
17	Correct	1177 ms	49988 KB	Output is correct
18	Correct	1118 ms	49004 KB	Output is correct
19	Correct	1523 ms	20972 KB	Output is correct
20	Correct	1900 ms	11500 KB	Output is correct
21	Correct	666 ms	3188 KB	Output is correct
22	Correct	2215 ms	15432 KB	Output is correct
23	Correct	743 ms	25708 KB	Output is correct
24	Correct	1584 ms	18456 KB	Output is correct
25	Correct	2606 ms	25996 KB	Output is correct
26	Correct	2251 ms	25964 KB	Output is correct
27	Correct	2164 ms	25320 KB	Output is correct
28	Correct	1131 ms	256000 KB	Output is correct
29	Runtime error	2152 ms	256004 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
30	Halted	0 ms	0 KB	-

Subtask #5

0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	364 KB	Output is correct
2	Correct	3 ms	620 KB	Output is correct
3	Correct	3 ms	620 KB	Output is correct
4	Correct	1 ms	364 KB	Output is correct
5	Correct	1 ms	364 KB	Output is correct
6	Correct	3 ms	620 KB	Output is correct
7	Correct	1 ms	364 KB	Output is correct
8	Correct	1 ms	364 KB	Output is correct
9	Correct	3 ms	620 KB	Output is correct
10	Correct	2 ms	492 KB	Output is correct
11	Correct	2 ms	492 KB	Output is correct
12	Correct	1080 ms	52460 KB	Output is correct
13	Correct	902 ms	53016 KB	Output is correct
14	Correct	1128 ms	49424 KB	Output is correct
15	Correct	1141 ms	49344 KB	Output is correct
16	Correct	774 ms	31212 KB	Output is correct
17	Correct	1149 ms	49516 KB	Output is correct
18	Correct	1147 ms	48940 KB	Output is correct
19	Correct	1540 ms	21100 KB	Output is correct
20	Correct	1917 ms	11228 KB	Output is correct
21	Correct	658 ms	3180 KB	Output is correct
22	Correct	2170 ms	15596 KB	Output is correct
23	Correct	739 ms	25944 KB	Output is correct
24	Correct	1571 ms	18284 KB	Output is correct
25	Correct	2573 ms	25668 KB	Output is correct
26	Correct	2252 ms	25896 KB	Output is correct
27	Correct	2144 ms	25324 KB	Output is correct
28	Correct	1140 ms	256000 KB	Output is correct
29	Runtime error	2149 ms	256004 KB	Execution killed with signal 9 (could be triggered by violating memory limits)
30	Halted	0 ms	0 KB	-