Submission #364454

#	Time	Username	Problem	Language	Result	Execution time	Memory
364454		thanksone	Game (IOI13_game)	C++14	100 / 100	4041 ms	171176 KiB

game

#include <game.h>
#include <bits/stdc++.h>
#define ff first
#define ss second
#define mid (l + r) / 2
using namespace std;
int R, C;
long long gcd(long long a, long long b){
    if(!b) return a;
    if(!a) return b;
    return gcd(b, a % b);
}
struct segleaf{
    long long val;
    pair<long long, int> tag;
    segleaf *lc, *rc;
    segleaf(){lc = rc = nullptr, val = 0, tag = {0, 0};}
    segleaf(long long v, int y){lc = rc = nullptr, val = v, tag = {v, y};}
    inline void pull(){
        val = gcd((lc? lc->val : 0), (rc? rc->val : 0));
    }
    inline void push(int m){
        if(tag.ff){
            if(tag.ss <= m) lc = new segleaf(tag.ff, tag.ss);
            else rc = new segleaf(tag.ff, tag.ss);
            tag = {0, 0};
        }
    }
    void update(int y, int l, int r, long long v){
        if(y == l && y == r){
            val = v;
            return;
        }
        push(mid);
        if(y <= mid){
            if(!lc)lc = new segleaf(v, y);
            else lc->update(y, l, mid, v);
        }else{
            if(!rc) rc = new segleaf(v, y);
            else rc->update(y, mid + 1, r, v);
        }
        pull();
    }
    long long query(int up, int down, int l, int r){
        if(tag.ff){
            if(tag.ss >= up && tag.ss <= down) return val;
            else return 0;
        }
        if(up == l && down == r) return val;
        push(mid);
        if(down <= mid) return (lc? lc->query(up, down, l, mid) : 0);
        else if(up > mid) return (rc? rc->query(up, down, mid + 1, r) : 0);
        else return gcd((lc? lc->query(up, mid, l, mid) : 0), (rc? rc->query(mid + 1, down, mid + 1, r) : 0));
    }
};
struct segtree{
    segleaf s;
    segtree *lc, *rc;
    segtree(){lc = rc = nullptr;}
    inline void pull(int y){
        s.update(y, 0, C - 1, gcd((lc? lc->s.query(y, y, 0, C - 1) : 0), (rc? rc->s.query(y, y, 0, C - 1) :0)));
    }
    void update(int x, int y, int l, int r, long long v){
        if(x == l && x == r){
            s.update(y, 0, C - 1, v);
            return;
        }
        if(x <= mid){
            if(!lc) lc = new segtree;
            lc->update(x, y, l, mid, v);
        }else{
            if(!rc) rc = new segtree;
            rc->update(x, y, mid + 1, r, v);
        }
        pull(y);
    }
    long long query(int left, int right, int up, int down, int l, int r){
        if(left == l && right == r) return s.query(up, down, 0, C - 1);
        else if(right <= mid) return (lc? lc->query(left, right, up, down, l, mid) : 0);
        else if(left > mid) return (rc? rc->query(left, right, up, down, mid + 1, r) : 0);
        else return gcd((lc? lc->query(left, mid, up, down, l, mid) : 0), (rc? rc->query(mid + 1, right, up, down, mid + 1, r) : 0));
    }
}root;
void init(int r, int c){
    R = r;
    C = c;
}
void update(int p, int q, long long k){
    root.update(p, q, 0, R - 1, k);
}
long long calculate(int l, int u, int r, int d){
    return root.query(l, r, u, d, 0, R - 1);
}

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