oj.uz

답안 #399573

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
399573 2021-05-06T06:35:12 Z achibasadzishvili 게임 (IOI13_game) C++17
0 / 100
 115 ms 256004 KB 
#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;
}
*/

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 114 ms 256004 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 115 ms 256004 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 107 ms 256004 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 110 ms 256004 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 111 ms 256004 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -