oj.uz

Submission #330353

# Submission time Handle Problem Language Result Execution time Memory
330353 2020-11-24T21:57:37 Z arwaeystoamneg Game (IOI13_game) C++17
63 / 100
 2575 ms 256004 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;
			
			getc(0)->update(x1, mid, x, y, val);
			getc(1)->update(mid + 1, x2, x, y, val);
			ll ans = gcd(C[0] ? C[0]->st.query(y, y) : 0, C[1] ? C[1]->st.query(y, y) : 0);
			st.update(y, ans);
		}
		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 1 ms 364 KB Output is correct
2 Correct 3 ms 768 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 1 ms 364 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory 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 1136 ms 54932 KB Output is correct
5 Correct 952 ms 54380 KB Output is correct
6 Correct 1157 ms 52460 KB Output is correct
7 Correct 1189 ms 51880 KB Output is correct
8 Correct 787 ms 33132 KB Output is correct
9 Correct 1189 ms 52460 KB Output is correct
10 Correct 1154 ms 52076 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 4 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 1576 ms 22836 KB Output is correct
13 Correct 1956 ms 13060 KB Output is correct
14 Correct 692 ms 5996 KB Output is correct
15 Correct 2239 ms 18528 KB Output is correct
16 Correct 781 ms 27756 KB Output is correct
17 Correct 1616 ms 21228 KB Output is correct
18 Correct 2550 ms 29420 KB Output is correct
19 Correct 2307 ms 29292 KB Output is correct
20 Correct 2226 ms 28864 KB Output is correct
21 Correct 1 ms 364 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 1162 ms 54756 KB Output is correct
13 Correct 927 ms 54380 KB Output is correct
14 Correct 1135 ms 52204 KB Output is correct
15 Correct 1204 ms 52204 KB Output is correct
16 Correct 777 ms 33132 KB Output is correct
17 Correct 1224 ms 52460 KB Output is correct
18 Correct 1193 ms 51820 KB Output is correct
19 Correct 1564 ms 22956 KB Output is correct
20 Correct 1971 ms 13120 KB Output is correct
21 Correct 701 ms 5996 KB Output is correct
22 Correct 2290 ms 18320 KB Output is correct
23 Correct 785 ms 27588 KB Output is correct
24 Correct 1633 ms 21152 KB Output is correct
25 Correct 2568 ms 29204 KB Output is correct
26 Correct 2249 ms 29420 KB Output is correct
27 Correct 2147 ms 28892 KB Output is correct
28 Runtime error 1131 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 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 4 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 1 ms 492 KB Output is correct
11 Correct 2 ms 492 KB Output is correct
12 Correct 1130 ms 54996 KB Output is correct
13 Correct 935 ms 54508 KB Output is correct
14 Correct 1155 ms 52440 KB Output is correct
15 Correct 1167 ms 51948 KB Output is correct
16 Correct 782 ms 33388 KB Output is correct
17 Correct 1191 ms 52588 KB Output is correct
18 Correct 1168 ms 51724 KB Output is correct
19 Correct 1588 ms 22880 KB Output is correct
20 Correct 1975 ms 13164 KB Output is correct
21 Correct 694 ms 5996 KB Output is correct
22 Correct 2245 ms 18156 KB Output is correct
23 Correct 772 ms 27756 KB Output is correct
24 Correct 1630 ms 21296 KB Output is correct
25 Correct 2575 ms 29260 KB Output is correct
26 Correct 2271 ms 29464 KB Output is correct
27 Correct 2191 ms 28684 KB Output is correct
28 Runtime error 1132 ms 256004 KB Execution killed with signal 9 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -