Submission #782774

#	Time	Username	Problem	Language	Result	Execution time	Memory
782774		FatihSolak	Game (IOI13_game)	C++17	100 / 100	4009 ms	16496 KiB

game

    #include "game.h"
    #include <algorithm>
    #include <iostream>
    #include <cassert>
    #include <cstdlib>
    #include <cstring>
    #include <cstdio>
    #include <cmath>
    #include <queue>
    #include <map>
    #include <set>
     
    using namespace std;
     
    #define type(x) __typeof((x).begin())
    #define foreach(i, x) for(type(x) i = (x).begin(); i != (x).end(); i++)
    #define y1 ___y1
     
    typedef long long ll;
    typedef pair < int, int > ii;
     
    const int inf = 1e9 + 333;
    const ll linf = 1e18 + 333;
     
    const int N = 22000;
    const int K = 92;
     
    class tree{ public: 
        int x, y, x1, y1, x2, y2;
        ll val, ans;
        tree *l, *r;
        tree() {
            x = y = x1 = y1 = x2 = y2 = -1;
            val = ans = 0;
            l = r = 0;
        }
    };
     
    typedef tree* pTree;
     
    int r, c, n, sz, type, x1, y1, x2, y2;
    ll k;
    map < ii, int > h;
    map < ii, ll > M;
    pair < ii, ll > a[N];
     
    inline ll gcd(ll a, ll b) {
        while(b) {
            a %= b;
            swap(a, b);
        }
        return a;
    }
     
    bool cmp(pair < ii, ll > x, pair < ii, ll > y) {
        if(x.first.second == y.first.second)
            return x.first.first < y.first.first;
        return x.first.second < y.first.second;
    }
     
    void init(pTree t, int l, int r, bool d = 0) {
        
        int m = l + r >> 1;
        
        if(!d)
            nth_element(a + l, a + m, a + r + 1);
        else
            nth_element(a + l, a + m, a + r + 1, cmp);
        
        t -> x = t -> x1 = t -> x2 = a[m].first.first;
        t -> y = t -> y1 = t -> y2 = a[m].first.second;
        t -> val = t -> ans = a[m].second;
        
        if(l < m) {
            if(!t -> l)
                t -> l = new tree;
            init(t -> l, l, m - 1, !d);
            t -> ans = gcd(t -> ans, t -> l -> ans);
            t -> x1 = min(t -> x1, t -> l -> x1);
            t -> y1 = min(t -> y1, t -> l -> y1);
            t -> x2 = max(t -> x2, t -> l -> x2);
            t -> y2 = max(t -> y2, t -> l -> y2);
        }
        
        if(m < r) {
            if(!t -> r)
                t -> r = new tree;
            init(t -> r, m + 1, r, !d);
            t -> ans = gcd(t -> ans, t -> r -> ans);
            t -> x1 = min(t -> x1, t -> r -> x1);
            t -> y1 = min(t -> y1, t -> r -> y1);
            t -> x2 = max(t -> x2, t -> r -> x2);
            t -> y2 = max(t -> y2, t -> r -> y2);
        }
        
    }
     
    ll query(pTree t) {
        
        if(x2 < t -> x1 or t -> x2 < x1 or y2 < t -> y1 or t -> y2 < y1)
            return 0;
        
        if(x1 <= t -> x1 and t -> x2 <= x2 and y1 <= t -> y1 and t -> y2 <= y2)
            return t -> ans;
        
        ll ans = 0;
        
        if(x1 <= t -> x and t -> x <= x2 and y1 <= t -> y and t -> y <= y2)
            ans = t -> val;
        
        if(t -> l)
            ans = gcd(ans, query(t -> l));
        
        if(t -> r)
            ans = gcd(ans, query(t -> r));
        
        return ans;
        
    }
     
    void change(pTree t, bool d = 0) {
        
        if(x1 == t -> x and y1 == t -> y) {
            t -> val = t -> ans = k;
            if(t -> l)
                t -> ans = gcd(t -> ans, t -> l -> ans);
            if(t -> r)
                t -> ans = gcd(t -> ans, t -> r -> ans);
            return;
        }
        
        if((!d and ii(x1, y1) < ii(t -> x, t -> y)) or (d and ii(y1, x1) < ii(t -> y, t -> x)))
            change(t -> l, !d);
        else
            change(t -> r, !d);
        
        t -> ans = t -> val;
        
        if(t -> l)
            t -> ans = gcd(t -> ans, t -> l -> ans);
        
        if(t -> r)
            t -> ans = gcd(t -> ans, t -> r -> ans);
        
    }
     
    pTree t;
     
    void init(int R, int C) {
    	r = R;
    	c = C;
    	t = new tree;
    }
     
    void update(int x1, int y1, ll k) {
    	:: x1 = x1;
    	:: y1 = y1;
    	:: k = k;
                if(h.find(ii(x1, y1)) != h.end()) {
                    change(t);
                    a[h[ii(x1, y1)]].second = k;
    				return;
                }
                M[ii(x1, y1)] = k;
                if(M.size() == K) {
                    foreach(it, M)
                        a[sz++] = *it;
                    M.clear();
                    init(t, 0, sz - 1);
                    for(int i = 0; i < sz; i++)
                        h[a[i].first] = i;
                }
    }
     
    ll calculate(int x1, int y1, int x2, int y2) {
    	:: x1 = x1;
    	:: y1 = y1;
    	:: x2 = x2;
    	:: y2 = y2;
                ll ans = query(t);
                foreach(it, M) {
                    int x = it -> first.first;
                    int y = it -> first.second;
                    ll k = it -> second;
                    if(x1 <= x and x <= x2 and y1 <= y and y <= y2)
                        ans = gcd(ans, k);
                }
    			return ans;
    }

Compilation message (stderr)

game.cpp: In function 'void init(pTree, int, int, bool)':
game.cpp:63:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   63 |         int m = l + r >> 1;
      |                 ~~^~~

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