oj.uz

Submission #16915

# Submission time Handle Problem Language Result Execution time Memory
16915 2015-10-24T17:59:13 Z erdemkiraz Game (IOI13_game) C++
100 / 100
 11235 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 2070 ms 3264 KB Output is correct
5 Correct 1162 ms 3264 KB Output is correct
6 Correct 1660 ms 3264 KB Output is correct
7 Correct 1746 ms 3264 KB Output is correct
8 Correct 918 ms 2604 KB Output is correct
9 Correct 1716 ms 3264 KB Output is correct
10 Correct 1858 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 1 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 4435 ms 3264 KB Output is correct
13 Correct 5900 ms 2868 KB Output is correct
14 Correct 761 ms 2076 KB Output is correct
15 Correct 5984 ms 2868 KB Output is correct
16 Correct 1001 ms 3264 KB Output is correct
17 Correct 1738 ms 2604 KB Output is correct
18 Correct 3844 ms 3264 KB Output is correct
19 Correct 3008 ms 3264 KB Output is correct
20 Correct 3498 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 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 2081 ms 3264 KB Output is correct
13 Correct 1155 ms 3264 KB Output is correct
14 Correct 1652 ms 3264 KB Output is correct
15 Correct 1739 ms 3264 KB Output is correct
16 Correct 941 ms 2604 KB Output is correct
17 Correct 1693 ms 3264 KB Output is correct
18 Correct 1864 ms 3264 KB Output is correct
19 Correct 4462 ms 3264 KB Output is correct
20 Correct 5962 ms 2868 KB Output is correct
21 Correct 773 ms 2076 KB Output is correct
22 Correct 6007 ms 2868 KB Output is correct
23 Correct 988 ms 3264 KB Output is correct
24 Correct 1745 ms 2604 KB Output is correct
25 Correct 3837 ms 3264 KB Output is correct
26 Correct 3017 ms 3264 KB Output is correct
27 Correct 3488 ms 3264 KB Output is correct
28 Correct 630 ms 3264 KB Output is correct
29 Correct 4621 ms 3264 KB Output is correct
30 Correct 6721 ms 3264 KB Output is correct
31 Correct 5579 ms 3000 KB Output is correct
32 Correct 782 ms 2076 KB Output is correct
33 Correct 942 ms 2076 KB Output is correct
34 Correct 1020 ms 3264 KB Output is correct
35 Correct 1878 ms 2604 KB Output is correct
36 Correct 3912 ms 3264 KB Output is correct
37 Correct 2993 ms 3264 KB Output is correct
38 Correct 3583 ms 3264 KB Output is correct
39 Correct 2424 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 2082 ms 3264 KB Output is correct
13 Correct 1157 ms 3264 KB Output is correct
14 Correct 1650 ms 3264 KB Output is correct
15 Correct 1726 ms 3264 KB Output is correct
16 Correct 941 ms 2604 KB Output is correct
17 Correct 1713 ms 3264 KB Output is correct
18 Correct 1848 ms 3264 KB Output is correct
19 Correct 4475 ms 3264 KB Output is correct
20 Correct 5967 ms 2868 KB Output is correct
21 Correct 791 ms 2076 KB Output is correct
22 Correct 6011 ms 2868 KB Output is correct
23 Correct 987 ms 3264 KB Output is correct
24 Correct 1735 ms 2604 KB Output is correct
25 Correct 3850 ms 3264 KB Output is correct
26 Correct 2985 ms 3264 KB Output is correct
27 Correct 3482 ms 3264 KB Output is correct
28 Correct 639 ms 3264 KB Output is correct
29 Correct 4622 ms 3264 KB Output is correct
30 Correct 6675 ms 3264 KB Output is correct
31 Correct 5514 ms 3000 KB Output is correct
32 Correct 814 ms 2076 KB Output is correct
33 Correct 941 ms 2076 KB Output is correct
34 Correct 996 ms 3264 KB Output is correct
35 Correct 1848 ms 2604 KB Output is correct
36 Correct 3887 ms 3264 KB Output is correct
37 Correct 3011 ms 3264 KB Output is correct
38 Correct 3553 ms 3264 KB Output is correct
39 Correct 1207 ms 4716 KB Output is correct
40 Correct 8251 ms 4716 KB Output is correct
41 Correct 11235 ms 4716 KB Output is correct
42 Correct 8594 ms 4056 KB Output is correct
43 Correct 1795 ms 4716 KB Output is correct
44 Correct 1082 ms 2076 KB Output is correct
45 Correct 2431 ms 3000 KB Output is correct
46 Correct 5693 ms 4716 KB Output is correct
47 Correct 5699 ms 4716 KB Output is correct
48 Correct 6607 ms 4716 KB Output is correct
49 Correct 0 ms 2076 KB Output is correct