Submission #1104886

#	Time	Username	Problem	Language	Result	Execution time	Memory
1104886		spycoderyt	Game (IOI13_game)	C++17	0 / 100	1 ms	336 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
// point update of val, 2d range gcd
long long  gcd(long long x, long long y) { return !y ? x : gcd(y, x % y); }
struct node{
    node *l,*r;
    int pos,key,ll,rr;
    long long val,g;
    node(int pos,long long k) {
        g = val = k;
        ll = rr = pos;
        key = rand();
    };
    void update(){
        g = val;
        if(l) g = gcd(g,l->g);
        if(r) g = gcd(g,r->g);
        ll = (l?l->ll : pos);
        rr = (r?r->rr : pos);
    }
};

struct treap{
    typedef node* pnode;
    pnode root;
    treap() {
        root=nullptr;
    }
    void split(pnode t, int pos,pnode& l,pnode& r) {
        if(!t) return void(l = r = nullptr);
        if(t->pos < pos) {
            split(t->r,pos,t->r,r);
        t->update();
            l = t;
        } else {
            split(t->l,pos,l,t->l);
        t->update();
            r = t;
        }
    }
    void merge(pnode& t,pnode l,pnode r) {
        if(!l || !r) return void(t = (l ? l : r));
        if(l->key > r->key) {
            merge(l->r,l->r,r);
            t = l;
        } else {
            merge(r->l,l,r->l);
            t = r;
        }
        t->update();
    }
    void upd(pnode& t, int pos,long long val) {
        if(t->pos == pos) {
            t->val = val;
            t->update();
            return;
        }
        if(pos > t->pos) upd(t->r,pos,val);
        else upd(t->l,pos,val);
        t->update();
    }
    bool find(int pos) {
        pnode t = root;
        while(t) {
            if(t->pos == pos) return 1;
            else if(pos > t->pos) t = t->r;
            else t = t->l;
        }
        return 0;
    }
    void insert(int pos,long long val) {
        if(find(pos)) upd(root,pos,val);
        else {
            pnode l,r,tmp;
            split(root,pos,l,r);
            merge(tmp,l,new node(pos,val));
            merge(root,tmp,r);
        }
    }
    long long query(pnode t,int ll,int rr) {
        if(t->rr < ll || t->ll > rr) return 0;
        if(t->ll >= ll && t->rr <= rr) return t->g;
        long long ans = (t->pos >= ll && t->pos <= rr ? t->val : 0);
        if(t->l) ans = gcd(ans,query(t->l,ll,rr));
        if(t->r) ans = gcd(ans,query(t->r,ll,rr));
        return ans;
    }
    long long qry(int ll,int rr) {
        if(!root)return 0;
        else return query(root,ll,rr);
    }
};

struct seg{
    seg *l,*r;
    treap t;
    int ll,rr;
    seg() {
        l = r = nullptr;
    }
    seg(int a,int b) {
        ll = a, rr = b;
        l = r = nullptr;
    }
    void new_left(){
        if(!l) l = new seg(ll,(ll+rr)/2);
    }
    void new_right(){
        if(!r) r = new seg((ll+rr)/2+1,rr);
    }
    void upd(int pos) {
        long long ans = 0;
        if(l) ans = gcd(ans,l->t.qry(pos,pos));
        if(r) ans = gcd(ans,r->t.qry(pos,pos));
        t.insert(pos,ans);
    }
    void upd(int x,int y,long long val) {
        if(x < ll || x > rr) return;
        if(ll==rr){
            t.insert(y,val);
            return;
        }
        if(x <= (ll+rr)/2) {
            new_left();
            l->upd(x,y,val);
        } else {
            new_right();
            r->upd(x,y,val);
        }
        upd(y);
    }
    long long query(int a,int b,int c,int d) {
        if(a > rr || b < ll) return 0;
        if(a >= ll && b <= rr) return t.qry(c,d);
        long long  ans = 0;
        if(l) ans = gcd(ans,l->query(a,b,c,d));
        if(r) ans = gcd(ans,r->query(a,b,c,d));
        return ans;
    }
};

seg tree;

void init(int R, int C) {
    tree = seg(0,R-1);
}

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

long long calculate(int P, int Q, int U, int V) {
    return tree.query(P,U,Q,V);
}

/*

/usr/bin/g++ -Wall -lm -static -DEVAL -o game -O2 -DEVAL grader.c game.cpp -std=c++11
./test



*/

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