Submission #552693

#	Time	Username	Problem	Language	Result	Execution time	Memory
552693		Jarif_Rahman	Game (IOI13_game)	C++17	0 / 100	58 ms	78160 KiB

game

#include "game.h"
#include <bits/stdc++.h>
#define pb push_back
#define f first
#define sc second
using namespace std;
typedef long long int ll;
typedef string str;

const int lim = 7e5;

struct Node{
    Node *l, *r;
    ll sm;
    Node(){
        l  = nullptr, r = nullptr;
        sm = 0;
    }
};

Node Nodes[lim];
int cntNodes = 0;

Node* newNode(){
    //return new Node();
    Nodes[cntNodes] = Node();
    return &Nodes[cntNodes++];
}

struct sparse_segtree{
    int n;
    Node* root;
    sparse_segtree(int _n){
        n = _n;
        root = newNode();
    }

    void upd(Node *nd, int l, int r, int in, ll x){
        if(l != r){
            if(in <= (l+r)/2){
                if(!nd->l) nd->l = newNode();
                upd(nd->l, l, (l+r)/2, in, x);
            }
            else{
                if(!nd->r) nd->r = newNode();
                upd(nd->r, (l+r)/2+1, r, in, x);
            }
            nd->sm = 0;
            if(nd->l) nd->sm = __gcd(nd->sm, nd->l->sm);
            if(nd->r) nd->sm = __gcd(nd->sm, nd->r->sm);
        }
        else nd->sm = x;
    }
    void upd(int in, ll x){
        upd(root, 0, n-1, in, x);
    }

    ll sum(Node* nd, int L, int R, int l, int r){
        if(L > r || R < l) return 0;
        if(L >= l && R <= r) return nd->sm;
        int md = (L+R)/2;
        ll rt = 0;
        if(nd->l) rt = __gcd(rt, sum(nd->l, L, md, l, r));
        if(nd->r) rt = __gcd(rt, sum(nd->r, md+1, R, l, r));
        return rt;
    }
    ll sum(int l, int r){
        return sum(root, 0, n-1, l, r);
    }

    ll get(Node *nd, int l, int r, int in){
        if(l == r) return nd->sm;
        if(in <= (l+r)/2) return (nd->l?get(nd->l, l, (l+r)/2, in):0);
        else return (nd->r?get(nd->r, (l+r)/2+1, r, in):0);
    }
    ll get(int in){
        return get(root, 0, n-1, in);
    }
};

struct Node2d{
    Node2d *l, *r;
    sparse_segtree sm = sparse_segtree(0);
    Node2d(){}
    Node2d(int m){
        l  = nullptr, r = nullptr;
        sm = sparse_segtree(m);
    }
};

Node2d Node2ds[lim];
int cntNode2ds = 0;

Node2d* newNode2d(int m){
    //return new Node2d(m);
    Node2ds[cntNode2ds] = Node2d(m);
    return &Node2ds[cntNode2ds++];
}

struct sparse_segtree2d{
    int n, m;
    Node2d* root;
    sparse_segtree2d(int _n, int _m){
        n = _n, m = _m;
        root = newNode2d(m);
    }

    void upd(Node2d *nd, int l, int r, int a, int b, ll x){
        if(l != r){
            if(a <= (l+r)/2){
                if(!nd->l) nd->l = newNode2d(m);
                upd(nd->l, l, (l+r)/2, a, b, x);
            }
            else{
                if(!nd->r) nd->r = newNode2d(m);
                upd(nd->r, (l+r)/2+1, r, a, b, x);
            }
            ll sm = 0;
            if(nd->l) sm = __gcd(sm, nd->l->sm.get(b));
            if(nd->r) sm = __gcd(sm, nd->r->sm.get(b));
            nd->sm.upd(b, sm);
        }
        else nd->sm.upd(b, x);
    }
    void upd(int a, int b, ll x){
        upd(root, 0, n-1, a, b, x);
    }

    ll sum(Node2d* nd, int L, int R, int a1, int b1, int a2, int b2){
        if(L > a2 || R < a1) return 0;
        if(L >= a1 && R <= a2) return nd->sm.sum(b1, b2);
        int md = (L+R)/2;
        ll rt = 0;
        if(nd->l) rt = __gcd(rt, sum(nd->l, L, md, a1, b1, a2, b2));
        if(nd->r) rt = __gcd(rt, sum(nd->r, md+1, R, a1, b1, a2, b2));
        return rt;
    }
    ll sum(int a1, int b1, int a2, int b2){
        return sum(root, 0, n-1, a1, b1, a2, b2);
    }
};

sparse_segtree2d sp(0, 0);

void init(int R, int C){
    sp = sparse_segtree2d(R+1, C+1);
}

void update(int P, int Q, long long K) {
    sp.upd(P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return sp.sum(P, Q, U, V);
}

• Subtask 1: 0 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20