| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 1203198 | CELD_07 | Game (IOI13_game) | C++20 | 0 ms | 0 KiB |
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#define ll long long
#define endl "\n"
#define inf LLONG_MAX
#define vll vector<ll>
#define sd second
#define ft first
#define all(x) x.begin(),x.end()
#define allr(x) x.rbegin(),x.rend()
#define pll pair<ll, ll>
#define mod 1000000007
#define _set tree<pll, null_type, less<pll>, rb_tree_tag, tree_order_statistics_node_update>
using namespace std;
using namespace __gnu_pbds;
int maxn=1000000005;
struct node1{
node1 *l, *r;
ll val;
node1(){
l=r=nullptr;
val=0;
}
};
inline void dely(node1 *v, int tl, int tr){
if(tl==tr){delete v;return;}
int tm=(tl+tr)/2;
if(v->l!=nullptr)dely(v->l, tl, tm);
if(v->r!=nullptr)dely(v->r, tm+1, tr);
delete v;
}
inline void update(node1 *v, node1 *v1, node1 *v2, int tl, int tr, int pos){
if(tl==tr){v->val=__gcd(v1->val, v2->val);return;}
int tm=(tl+tr)/2;
if(pos<=tm){
if(v->l==nullptr)v->l=new node1();
if(v1->l==nullptr)v1->l=new node1();
if(v2->l==nullptr)v2->l=new node1();
update(v->l, v1->l, v2->l, tl, tm, pos);
}else {
if(v->r==nullptr)v->r=new node1();
if(v1->r==nullptr)v1->r=new node1();
if(v2->r==nullptr)v2->r=new node1();
update(v->r, v1->r, v2->r, tm+1, tr, pos);
}
if(v->l==nullptr)v->val=v->r->val;
else if(v->r==nullptr)v->val=v->l->val;
else v->val=__gcd(v->l->val, v->r->val);
}
inline void updatel(node1 *v, int tl, int tr, int pos, ll val1){
//cout<<tl<<" "<<tr<<endl;
if(tl==tr){v->val=val1;return;}
int tm=(tl+tr)/2;
if(pos<=tm){
if(v->l==nullptr)v->l=new node1();
updatel(v->l, tl, tm, pos, val1);
}else {
if(v->r==nullptr)v->r=new node1();
updatel(v->r, tm+1, tr, pos, val1);
}
if(v->l==nullptr)v->val=v->r->val;
else if(v->r==nullptr)v->val=v->l->val;
else v->val=__gcd(v->l->val, v->r->val);
}
inline ll query(node1 *v, int tl, int tr, int l, int r){
if(tl>r || tr<l)return 0LL;
if(tl>=l && tr<=r)return v->val;
ll tm=(tl+tr)/2;
if(v->l==nullptr && v->r==nullptr)return 0;
if(v->l==nullptr)return query(v->r, tm+1, tr, l, r);
else if(v->r==nullptr)return query(v->l, tl, tm, l, r);
else return __gcd(query(v->l, tl, tm, l, r), query(v->r, tm+1, tr, l, r));
}
struct node{
node *l, *r;
ll val;
node1* t;
node(){
l=r=nullptr;
t=new node1();
val=0;
}
};
inline void delx(node *v, int tl, int tr){
if(tl==tr)dely(v->t, 0, maxn);
else{
int tm=(tl+tr)/2;
if(v->l)delx(v->l, tl, tm);
if(v->r)delx(v->r, tm+1, tr);
dely(v->t, 0, maxn);
}
}
inline void updatey(node* v, int tl, int tr, int x, int y, ll val){
if(tl==tr){
updatel(v->t, 0, maxn, y, val);
return;
}
//cout<<tl<<" "<<tr<<endl;
int tm=(tl+tr)/2;
if(x<=tm){
if(v->l==nullptr)v->l=new node();
updatey(v->l, tl, tm, x, y, val);
}else{
if(v->r==nullptr)v->r=new node();
updatey(v->r, tm+1, tr, x, y, val);
}
if(v->l ==nullptr)v->l=new node();
if(v->r ==nullptr)v->r=new node();
update(v->t, v->l->t, v->r->t, 0, maxn, y);
}
inline ll query(node* v, int tl, int tr, int xl, int yl, int xr, int yr){
if(tl>xr || tr<xl)return 0;
if(tl>=xl && tr<=xr)return query(v->t, 0,maxn, yl, yr);
int tm=(tl+tr)/2;
if(v->l==nullptr && v->r==nullptr)return 0;
if(v->r==nullptr)return query(v->l, tl, tm, xl, yl, xr, yr);
if(v->l==nullptr)return query(v->r, tm+1, tr, xl, yl, xr, yr);
return __gcd(query(v->l, tl, tm, xl, yl, xr, yr), query(v->r, tm+1, tr, xl, yl, xr, yr));
}
node *t=nullptr;
void init(int R, int C){
if(t)delx(t, 0, maxn);
t=new node();
}
void update(int P, int Q, long long K){
updatey(t, 0, maxn, P, Q, K);
}
long long calculate(int P, int Q, int U, int V){
return query(t, 0, maxn, P, Q, U, V);
}