#include<bits/stdc++.h>
#include "game.h"
#define ll long long
#define f first
#define s second
#define pb push_back
using namespace std;
ll s1 = 1, s2 = 1;
ll gcd(ll x,ll y){
return __gcd(x , y);
}
struct T {ll x; int p = 0,l,r;} X[50000000];
struct seg1 {
int N,root;
seg1(int n) : N(n){root = 0;}
ll get(int root,int L,int R,int l,int r){
if(L > r || R < l || !root)return 0;
if(L >= l && R <= r){
return X[root].x;
}
if(X[root].p){
if(X[root].p >= l && X[root].p <= r)return X[root].x;
return 0;
}
int mid = (L + R) / 2;
ll k1 = get(X[root].l , L , mid , l , r);
ll k2 = get(X[root].r , mid + 1 , R , l , r);
return gcd(k1 , k2);
}
ll get(int l,int r){
return get(root , 0 , N , l , r);
}
ll set(int& root,int L,int R,int ind,ll cur){
if(ind > R || ind < L)return X[root].x;
if(!root){
root = s1++;
X[root].x = cur;
X[root].p = ind;
return cur;
}
if(L == R){
return X[root].x = cur;
}
int mid = (L + R) / 2;
if(X[root].p){
set(X[root].l , L , mid , X[root].p , X[root].x);
set(X[root].r , mid + 1 , R , X[root].p , X[root].x);
X[root].p = 0;
}
ll k1 = set(X[root].l , L , mid , ind , cur);
ll k2 = set(X[root].r , mid + 1 , R , ind , cur);
return X[root].x = gcd(k1 , k2);
}
void set(int x,ll y){
set(root , 0 , N , x , y);
}
};
struct T2 {seg1* x; int l,r;} Y[50000000];
struct seg2 {
int N,M,root;
seg2(int n,int m) : N(n) , M(m) {root = 0;}
ll get(int root ,int L,int R,int l,int r,int nl,int nr){
if(L > r || R < l || !root)return 0;
//cout << L << " " << R << '\n';
if(L >= l && R <= r){
//cout << L << " " << nl << " " << nr << " " << root << '\n';
//cout << Y[root].x -> get(nl , nr) << '\n';
return Y[root].x -> get(nl,nr);
}
int mid = (L + R) / 2;
ll k1 = get(Y[root].l , L , mid , l , r , nl , nr);
ll k2 = get(Y[root].r , mid + 1 , R , l , r , nl , nr);
return gcd(k1 , k2);
}
ll get(int a,int b,int c,int d){
return get(root , 0 , N , a , b , c , d);
}
ll set(int& root,int L,int R,int ind,int nind,ll cur){
if(ind < L || ind > R){
if(!root)return 0;
else return Y[root].x -> get(nind , nind);
}
if(!root){
root = s2++;
Y[root].x = new seg1(M);
}
//cout << root << " " << L << " " << R << '\n';
if(L == R){
if(root == 5){
//cout << nind << " - " << cur << '\n';
}
Y[root].x -> set(nind , cur);
return cur;
}
int mid = (L + R) / 2;
ll k1 = set(Y[root].l , L , mid , ind, nind , cur);
ll k2 = set(Y[root].r , mid + 1 , R , ind , nind , cur);
ll y = gcd(k1 , k2);
Y[root].x -> set(nind , y);
return y;
}
void set(int a,int b,ll c){
set(root , 0 , N , a , b , c);
}
} *T;
void init(int R,int C){
T = new seg2(R + 10 , C + 10);
}
void update(int x,int y,ll z){
x++;
y++;
T -> set(x , y , z);
}
ll calculate(int a,int b,int c,int d){
a++;b++;c++;d++;
return T -> get(a , c , b, d);
}
/*
int main(){
ios::sync_with_stdio(false);
ll n,m,q;
cin >> n >> m >> q;
init(n , m);
while(q--){
ll typ;
cin >> typ;
if(typ == 1){
ll x,y,z;
cin >> x >> y >> z;
update(x , y , z);
}
else {
int a,b,c,d;
cin >> a >> b >> c >> d;
cout << calculate(a , b , c, d) << '\n';
}
}
return 0;
}
*/
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
114 ms |
256004 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
115 ms |
256004 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
107 ms |
256004 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
110 ms |
256004 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
111 ms |
256004 KB |
Execution killed with signal 9 |
| 2 |
Halted |
0 ms |
0 KB |
- |
