oj.uz

Submission #16914

# Submission time Handle Problem Language Result Execution time Memory
16914 2015-10-24T17:52:05 Z erdemkiraz Game (IOI13_game) C++
100 / 100
 11100 ms 4716 KB 
#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.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2076 KB Output is correct
2 Correct 0 ms 2076 KB Output is correct
3 Correct 0 ms 2076 KB Output is correct
4 Correct 0 ms 2076 KB Output is correct
5 Correct 0 ms 2076 KB Output is correct
6 Correct 0 ms 2076 KB Output is correct
7 Correct 0 ms 2076 KB Output is correct
8 Correct 0 ms 2076 KB Output is correct
9 Correct 0 ms 2076 KB Output is correct
10 Correct 0 ms 2076 KB Output is correct
11 Correct 0 ms 2076 KB Output is correct
12 Correct 0 ms 2076 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2076 KB Output is correct
2 Correct 0 ms 2076 KB Output is correct
3 Correct 0 ms 2076 KB Output is correct
4 Correct 2058 ms 3264 KB Output is correct
5 Correct 1155 ms 3264 KB Output is correct
6 Correct 1665 ms 3264 KB Output is correct
7 Correct 1730 ms 3264 KB Output is correct
8 Correct 937 ms 2604 KB Output is correct
9 Correct 1692 ms 3264 KB Output is correct
10 Correct 1841 ms 3264 KB Output is correct
11 Correct 0 ms 2076 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2076 KB Output is correct
2 Correct 0 ms 2076 KB Output is correct
3 Correct 0 ms 2076 KB Output is correct
4 Correct 0 ms 2076 KB Output is correct
5 Correct 0 ms 2076 KB Output is correct
6 Correct 0 ms 2076 KB Output is correct
7 Correct 0 ms 2076 KB Output is correct
8 Correct 0 ms 2076 KB Output is correct
9 Correct 0 ms 2076 KB Output is correct
10 Correct 0 ms 2076 KB Output is correct
11 Correct 0 ms 2076 KB Output is correct
12 Correct 4457 ms 3264 KB Output is correct
13 Correct 5950 ms 2868 KB Output is correct
14 Correct 771 ms 2076 KB Output is correct
15 Correct 6010 ms 2868 KB Output is correct
16 Correct 990 ms 3264 KB Output is correct
17 Correct 1762 ms 2604 KB Output is correct
18 Correct 3855 ms 3264 KB Output is correct
19 Correct 2996 ms 3264 KB Output is correct
20 Correct 3500 ms 3264 KB Output is correct
21 Correct 0 ms 2076 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2076 KB Output is correct
2 Correct 0 ms 2076 KB Output is correct
3 Correct 0 ms 2076 KB Output is correct
4 Correct 0 ms 2076 KB Output is correct
5 Correct 1 ms 2076 KB Output is correct
6 Correct 0 ms 2076 KB Output is correct
7 Correct 0 ms 2076 KB Output is correct
8 Correct 0 ms 2076 KB Output is correct
9 Correct 0 ms 2076 KB Output is correct
10 Correct 0 ms 2076 KB Output is correct
11 Correct 0 ms 2076 KB Output is correct
12 Correct 2077 ms 3264 KB Output is correct
13 Correct 1157 ms 3264 KB Output is correct
14 Correct 1649 ms 3264 KB Output is correct
15 Correct 1723 ms 3264 KB Output is correct
16 Correct 947 ms 2604 KB Output is correct
17 Correct 1690 ms 3264 KB Output is correct
18 Correct 1847 ms 3264 KB Output is correct
19 Correct 4409 ms 3264 KB Output is correct
20 Correct 5915 ms 2868 KB Output is correct
21 Correct 786 ms 2076 KB Output is correct
22 Correct 6051 ms 2868 KB Output is correct
23 Correct 1006 ms 3264 KB Output is correct
24 Correct 1732 ms 2604 KB Output is correct
25 Correct 3856 ms 3264 KB Output is correct
26 Correct 2996 ms 3264 KB Output is correct
27 Correct 3494 ms 3264 KB Output is correct
28 Correct 628 ms 3264 KB Output is correct
29 Correct 4642 ms 3264 KB Output is correct
30 Correct 6755 ms 3264 KB Output is correct
31 Correct 5570 ms 3000 KB Output is correct
32 Correct 840 ms 2076 KB Output is correct
33 Correct 914 ms 2076 KB Output is correct
34 Correct 1001 ms 3264 KB Output is correct
35 Correct 1817 ms 2604 KB Output is correct
36 Correct 3896 ms 3264 KB Output is correct
37 Correct 2956 ms 3264 KB Output is correct
38 Correct 3583 ms 3264 KB Output is correct
39 Correct 2419 ms 3000 KB Output is correct
40 Correct 0 ms 2076 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 2076 KB Output is correct
2 Correct 0 ms 2076 KB Output is correct
3 Correct 0 ms 2076 KB Output is correct
4 Correct 0 ms 2076 KB Output is correct
5 Correct 0 ms 2076 KB Output is correct
6 Correct 0 ms 2076 KB Output is correct
7 Correct 0 ms 2076 KB Output is correct
8 Correct 0 ms 2076 KB Output is correct
9 Correct 0 ms 2076 KB Output is correct
10 Correct 0 ms 2076 KB Output is correct
11 Correct 0 ms 2076 KB Output is correct
12 Correct 2077 ms 3264 KB Output is correct
13 Correct 1175 ms 3264 KB Output is correct
14 Correct 1682 ms 3264 KB Output is correct
15 Correct 1737 ms 3264 KB Output is correct
16 Correct 936 ms 2604 KB Output is correct
17 Correct 1687 ms 3264 KB Output is correct
18 Correct 1826 ms 3264 KB Output is correct
19 Correct 4469 ms 3264 KB Output is correct
20 Correct 5921 ms 2868 KB Output is correct
21 Correct 786 ms 2076 KB Output is correct
22 Correct 6044 ms 2868 KB Output is correct
23 Correct 1000 ms 3264 KB Output is correct
24 Correct 1755 ms 2604 KB Output is correct
25 Correct 3862 ms 3264 KB Output is correct
26 Correct 3020 ms 3264 KB Output is correct
27 Correct 3481 ms 3264 KB Output is correct
28 Correct 632 ms 3264 KB Output is correct
29 Correct 4658 ms 3264 KB Output is correct
30 Correct 6727 ms 3264 KB Output is correct
31 Correct 5569 ms 3000 KB Output is correct
32 Correct 784 ms 2076 KB Output is correct
33 Correct 952 ms 2076 KB Output is correct
34 Correct 990 ms 3264 KB Output is correct
35 Correct 1853 ms 2604 KB Output is correct
36 Correct 3917 ms 3264 KB Output is correct
37 Correct 2998 ms 3264 KB Output is correct
38 Correct 3592 ms 3264 KB Output is correct
39 Correct 1203 ms 4716 KB Output is correct
40 Correct 8328 ms 4716 KB Output is correct
41 Correct 11100 ms 4716 KB Output is correct
42 Correct 8736 ms 4056 KB Output is correct
43 Correct 1811 ms 4716 KB Output is correct
44 Correct 1074 ms 2076 KB Output is correct
45 Correct 2408 ms 3000 KB Output is correct
46 Correct 5722 ms 4716 KB Output is correct
47 Correct 5707 ms 4716 KB Output is correct
48 Correct 6640 ms 4716 KB Output is correct
49 Correct 0 ms 2076 KB Output is correct