답안 #16915 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
16915	2015-10-24T17:59:13 Z	erdemkiraz	게임 (IOI13_game)	C++	100 / 100	11235 ms	4716 KB

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.0 / 10.0

#	결과	메모리	Grader output
1	Correct	2076 KB	Output is correct
2	Correct	2076 KB	Output is correct
3	Correct	2076 KB	Output is correct
4	Correct	2076 KB	Output is correct
5	Correct	2076 KB	Output is correct
6	Correct	2076 KB	Output is correct
7	Correct	2076 KB	Output is correct
8	Correct	2076 KB	Output is correct
9	Correct	2076 KB	Output is correct
10	Correct	2076 KB	Output is correct
11	Correct	2076 KB	Output is correct
12	Correct	2076 KB	Output is correct

Subtask #2
27.0 / 27.0

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

#	결과	실행 시간	메모리	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

답안 #16915

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 27.0 / 27.0

Subtask #3 26.0 / 26.0

Subtask #4 17.0 / 17.0

Subtask #5 20.0 / 20.0

Subtask #1
10.0 / 10.0

Subtask #2
27.0 / 27.0

Subtask #3
26.0 / 26.0

Subtask #4
17.0 / 17.0

Subtask #5
20.0 / 20.0