답안 #16914 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
16914	2015-10-24T17:52:05 Z	erdemkiraz	게임 (IOI13_game)	C++	100 / 100	11100 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	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

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

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

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

답안 #16914

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