oj.uz

Submission #330354

# Submission time Handle Problem Language Result Execution time Memory
330354 2020-11-24T22:02:18 Z arwaeystoamneg Game (IOI13_game) C++17
63 / 100
 2587 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;
			if (x <= mid)
				getc(0)->update(x1, mid, x, y, val);
			else if (x > mid)
				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 620 KB Output is correct
3 Correct 3 ms 640 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 1110 ms 50284 KB Output is correct
5 Correct 913 ms 50552 KB Output is correct
6 Correct 1102 ms 47468 KB Output is correct
7 Correct 1160 ms 47388 KB Output is correct
8 Correct 755 ms 29028 KB Output is correct
9 Correct 1182 ms 47724 KB Output is correct
10 Correct 1152 ms 47084 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 2 ms 364 KB Output is correct
2 Correct 3 ms 620 KB Output is correct
3 Correct 4 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 1587 ms 18924 KB Output is correct
13 Correct 1979 ms 9196 KB Output is correct
14 Correct 678 ms 1260 KB Output is correct
15 Correct 2277 ms 13676 KB Output is correct
16 Correct 767 ms 23404 KB Output is correct
17 Correct 1602 ms 16368 KB Output is correct
18 Correct 2585 ms 23732 KB Output is correct
19 Correct 2293 ms 24060 KB Output is correct
20 Correct 2203 ms 23328 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 1 ms 492 KB Output is correct
11 Correct 2 ms 492 KB Output is correct
12 Correct 1122 ms 50412 KB Output is correct
13 Correct 911 ms 50412 KB Output is correct
14 Correct 1110 ms 47596 KB Output is correct
15 Correct 1152 ms 47468 KB Output is correct
16 Correct 756 ms 28928 KB Output is correct
17 Correct 1173 ms 47724 KB Output is correct
18 Correct 1140 ms 47048 KB Output is correct
19 Correct 1585 ms 18976 KB Output is correct
20 Correct 1993 ms 9068 KB Output is correct
21 Correct 679 ms 1388 KB Output is correct
22 Correct 2275 ms 13720 KB Output is correct
23 Correct 747 ms 23404 KB Output is correct
24 Correct 1578 ms 16236 KB Output is correct
25 Correct 2563 ms 23996 KB Output is correct
26 Correct 2282 ms 24044 KB Output is correct
27 Correct 2232 ms 23276 KB Output is correct
28 Correct 1118 ms 256000 KB Output is correct
29 Runtime error 2113 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 1114 ms 50676 KB Output is correct
13 Correct 917 ms 50608 KB Output is correct
14 Correct 1139 ms 47704 KB Output is correct
15 Correct 1159 ms 47392 KB Output is correct
16 Correct 766 ms 29036 KB Output is correct
17 Correct 1161 ms 47980 KB Output is correct
18 Correct 1126 ms 47212 KB Output is correct
19 Correct 1598 ms 18684 KB Output is correct
20 Correct 2001 ms 9128 KB Output is correct
21 Correct 675 ms 1516 KB Output is correct
22 Correct 2260 ms 13728 KB Output is correct
23 Correct 765 ms 23472 KB Output is correct
24 Correct 1616 ms 16480 KB Output is correct
25 Correct 2587 ms 23968 KB Output is correct
26 Correct 2280 ms 24044 KB Output is correct
27 Correct 2206 ms 23592 KB Output is correct
28 Correct 1130 ms 256000 KB Output is correct
29 Runtime error 2105 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
30 Halted 0 ms 0 KB -