oj.uz

답안 #330359

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
330359 2020-11-24T22:26:11 Z arwaeystoamneg 게임 (IOI13_game) C++17
63 / 100
 2606 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);
				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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 -