Submission #16915

#	Time	Username	Problem	Language	Result	Execution time	Memory
16915		erdemkiraz	Game (IOI13_game)	C++98	100 / 100	11235 ms	4716 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;
}

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