oj.uz

Submission #400220

# Submission time Handle Problem Language Result Execution time Memory
400220 2021-05-07T16:48:34 Z Antekb Game (IOI13_game) C++14
0 / 100
 3 ms 588 KB 
#include "game.h"
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=(1<<30);
long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

struct node{
    ll val=0;
    node* l=nullptr, *r=nullptr;
    node(ll _val): val(_val){}
};
ll val(node*v){
    if(v)return v->val;
    return 0;
}
node* left(node* v){
    if(v)return v->l;
    return nullptr;
}
node* right(node* v){
    if(v)return v->r;
    return nullptr;
}
void upd(node* v){
    if(!v)return;
    v->val=gcd2(val(left(v)), val(right(v)));
}
ll quer1d(node* v, int L, int R, int l, int r){
    if(!v)return 0;
    //cout<<L<<" "<<R<<" "<<v->val<<"q\n";
    if(l==L && r==R){
        return val(v);
    }
    int M=(L+R)>>1;
    ll ans=0;
    if(l<=M)ans=gcd2(ans, quer1d(left(v), L, M, l, min(M, r)));
    if(r>M)ans=gcd2(ans, quer1d(right(v), M+1, R, max(l, M+1), r));
    return ans;
}
node* upd1d(node* v, int L, int R, int i, ll val){
    if(!v)v=new node(0);
    if(L==R){
        v->val=val;
        return v;
    }
    int M=(L+R)>>1;
    if(i<=M)v->l=upd1d(v->l, L, M, i, val);
    else v->r=upd1d(v->r, M+1, R, i, val);
    upd(v);
    //cout<<L<<" "<<R<<" "<<v->val<<"\n";
    return v;
}
struct node2{
    node* val=nullptr;
    node2* l=nullptr, *r=nullptr;
    node2(node* _v): val(_v){}
};
node* val(node2* v){
    if(v)return v->val;
    return 0;
}
node2* left(node2* v){
    if(v)return v->l;
    return nullptr;
}
node2* right(node2* v){
    if(v)return v->r;
    return nullptr;
}
ll quer2d(node2* v, int L, int R, int l, int r, int x, int y){
    if(!v)return 0;
    if(l==L && r==R){
        return quer1d(val(v), 0, N-1, x, y);
    }
    int M=(L+R)>>1;
    ll ans=0;
    if(l<=M)ans=gcd2(ans, quer2d(left(v), L, M, l, min(M, r), x, y));
    if(r>M)ans=gcd2(ans, quer2d(right(v), M+1, R, max(l, M+1), r, x, y));
    return ans;
}
node2* upd2d(node2* v, int L, int R, int i, int j, ll val){
    if(!v)v=new node2(nullptr);
    v->val=upd1d(v->val, 0, N-1, j, val);
    if(L==R){
        return v;
    }
    int M=(L+R)>>1;
    if(i<=M)v->l=upd2d(left(v), L, M, i, j, val);
    else v->r=upd2d(right(v), M+1, R, i, j, val);
    return v;
}
node2* root=nullptr;
void init(int R, int C) {
    /* ... */
}

void update(int P, int Q, long long K) {
    root=upd2d(root, 0, N-1, P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return quer2d(root, 0, N-1, P, U, Q, V);
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Incorrect 3 ms 588 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Incorrect 1 ms 332 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 3 ms 588 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Incorrect 3 ms 588 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 208 KB Output is correct
2 Incorrect 3 ms 588 KB Output isn't correct
3 Halted 0 ms 0 KB -