oj.uz

Submission #364452

# Submission time Handle Problem Language Result Execution time Memory
364452 2021-02-09T08:22:25 Z thanksone Game (IOI13_game) C++14
0 / 100
 1 ms 384 KB 
#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(int a, int 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
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 364 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 364 KB Output is correct
2 Correct 1 ms 256 KB Output is correct
3 Incorrect 1 ms 364 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Incorrect 1 ms 384 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 364 KB Output is correct
2 Incorrect 1 ms 364 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 364 KB Output is correct
2 Incorrect 1 ms 364 KB Output isn't correct
3 Halted 0 ms 0 KB -