| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 361610 | gratus907 | 조화행렬 (KOI18_matrix) | C++17 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC target("avx,avx2,fma")
#define ll long long
#define int ll
#define eps 1e-7
#define all(x) ((x).begin()),((x).end())
#define usecppio ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
const int MAXR = 1000000007;
const int MAXC = 1000000007;
// max-dynamic-2seg
// msg555 impl, some modifications
void init(int32_t R, int32_t C) {}
int agg(int a, int b) {return __gcd(a, b);}
struct Dynamic2DSeg
{
struct Node
{
Node (int l, int r, int v = 0) : l(l), r(r), v(v), lc(NULL), rc(NULL){}
int l, r, v;
Node *lc, *rc;
};
struct RowNode
{
RowNode () : lc(NULL), rc(NULL), rowRoot(0, MAXC){}
Node rowRoot;
RowNode *lc, *rc;
};
RowNode root;
static void update2(Node *node, int idx, int dt)
{
int lo = node -> l;
int hi = node -> r;
int mid = (lo + hi) / 2;
if (lo + 1 == hi)
{
node -> v = dt;
return;
}
Node *& next = idx < mid ? node -> lc : node -> rc;
if (next == NULL)
next = new Node(idx, idx + 1, dt);
else if (next -> l <= idx && idx <= next -> r)
update2(next, idx, dt);
else
{
do {
(idx < mid ? hi : lo) = mid;
mid = (lo + hi) / 2;
} while ((idx < mid) == (next->l < mid));
Node * nnode = new Node(lo, hi);
(next->l < mid ? nnode->lc : nnode->rc) = next;
next = nnode;
update2(nnode, idx, dt);
}
node -> v = agg(node->lc?node->lc->v:0, node->rc?node->rc->v:0);
}
static void update1(RowNode * node, int lo, int hi, int ridx, int idx, int dt)
{
int mid = (lo + hi) / 2;
if (lo + 1 == hi)
update2(&node -> rowRoot, idx, dt);
else
{
RowNode *& nnode = ridx < mid ? node -> lc : node -> rc;
(ridx < mid ? hi : lo) = mid;
if (nnode == NULL)
nnode = new RowNode();
update1(nnode, lo, hi, ridx, idx, dt);
dt = agg(node->lc ? query2(&node->lc->rowRoot, idx, idx + 1) : 0,
node->rc ? query2(&node->rc->rowRoot, idx, idx + 1) : 0);
update2(&node->rowRoot, idx, dt);
}
}
static int query2(Node *node, int a, int b)
{
if (node == NULL || b <= node -> l || node -> r <= a)
return 0;
else if (a <= node -> l && node -> r <= b)
return node -> v;
return agg(query2(node->lc, a, b), query2(node->rc, a, b));
}
static int query1(RowNode *node, int lo, int hi, int a1, int b1, int a2, int b2)
{
if (node == NULL || b1 <= lo || hi <= a1)
return 0;
else if (a1 <= lo && hi <= b1)
return query2(&node->rowRoot, a2, b2);
int mid = (lo + hi) / 2;
return agg(query1(node->lc, lo, mid, a1, b1, a2, b2),
query1(node->rc, mid, hi, a1, b1, a2, b2));
}
void update(int x, int y, int dt)
{
update1(&root, 0, MAXR, x, y, dt);
}
int query(int x1, int y1, int x2, int y2)
{
return query1(&root, 0, MAXR, x1, x2 + 1, y1, y2 + 1);
}
} DSEG;
void update(int32_t P,int32_t Q,long long K)
{
DSEG.update(P, Q, K);
}
long long calculate(int32_t P,int32_t Q,int32_t U,int32_t V){
return DSEG.query1(P, Q, U, V);
}