#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]->st.query(y, y), C[1] ? C[1]->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);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
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 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 4 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Runtime error |
1 ms |
492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 ms |
364 KB |
Output is correct |
| 2 |
Runtime error |
2 ms |
492 KB |
Execution killed with signal 11 (could be triggered by violating memory limits) |
| 3 |
Halted |
0 ms |
0 KB |
- |
