oj.uz

Submission #416719

# Submission time Handle Problem Language Result Execution time Memory
416719 2021-06-02T20:35:05 Z Tangent Game (IOI13_game) C++17
63 / 100
 13000 ms 59036 KB 
#include "game.h"
#include "bits/stdc++.h"

using namespace std;

typedef long long ll;
typedef vector<ll> vll;
typedef vector<int> vii;
typedef vector<vll> vvll;
typedef vector<vii> vvii;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef vector<pii> vpii;
typedef vector<vpll> vvpll;
typedef vector<vpii> vvpii;

#define ffor(i, a, b) for (ll i = a; i < b; i++)
#define rep(i, n) ffor(i, 0, n)
#define forin(x, a) for (auto &x: a)
#define all(x) x.begin(), x.end()

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

ll r, c;
unordered_map<ll, ll> t;

ll gett(int y, int x) {
    ll k = 4 * r * y + x;
    if (t.find(k) == t.end()) {
        return 0;
    }
    return t[k];
}

void sett(int y, int x, ll v) {
    ll k = 4 * r * y + x;
    if (v) {
        t[k] = v;
    } else {
        t.erase(k);
    }
    // cout << y << ' ' << x << ' ' << v << '\n';
}

void init(int R, int C) {
    r = R;
    c = C;
}



void upd2(int y, int x, long long v, int y1, int y2, int x1, int x2, int yt, int xt) {
    if (y1 == y2) {
        if (x1 == x2) {
            sett(y, x, v);
        } else {
            sett(y, x, gcd2(gett(y, 2 * x), gett(y, 2 * x + 1)));
        }
    } else {
        int my = (y1 + y2) / 2;
        if (yt <= my) {
            upd2(y * 2, x, v, y1, my, x1, x2, yt, xt);
        } else {
            upd2(y * 2 + 1, x, v, my + 1, y2, x1, x2, yt, xt);
        }
        sett(y, x, gcd2(gett(y * 2, x), gett(y * 2 + 1, x)));
    }
}

void upd(int y, int x, long long v, int y1, int y2, int x1, int x2, int yt, int xt) {
    if (x1 != x2) {
        int mx = (x1 + x2) / 2;
        if (xt <= mx) {
            upd(y, x * 2, v, y1, y2, x1, mx, yt, xt);
        } else {
            upd(y, x * 2 + 1, v, y1, y2, mx + 1, x2, yt, xt);
        }
    }
    upd2(y, x, v, y1, y2, x1, x2, yt, xt);
}

void update(int P, int Q, long long K) {
    upd(1, 1, K, 0, c - 1, 0, r - 1, Q, P);
}

ll query(int y, int x, int y1, int y2, int x1, int x2, int yt1, int xt1, int yt2, int xt2) {
    if (x1 == xt1 && x2 == xt2) {
        if (y1 == yt1 && y2 == yt2) {
            return gett(y, x);
        } else {
            int my = (y1 + y2) / 2;
            ll res = 0;
            if (yt1 <= my) {
                res = gcd2(res, query(y * 2, x, y1, my, x1, x2, yt1, xt1, min(yt2, my), xt2));
            }
            if (yt2 > my) {
                res = gcd2(res, query(y * 2 + 1, x, my + 1, y2, x1, x2, max(yt1, my + 1), xt1, yt2, xt2));
            }
            return res;
        }
    } else {
        int mx = (x1 + x2) / 2;
        ll res = 0;
        if (xt1 <= mx) {
            res = gcd2(res, query(y, x * 2, y1, y2, x1, mx, yt1, xt1, yt2, min(xt2, mx)));
        }
        if (xt2 > mx) {
            res = gcd2(res, query(y, x * 2 + 1, y1, y2, mx + 1, x2, yt1, max(xt1, mx + 1), yt2, xt2));
        }
        return res;
    }
}

long long calculate(int x1, int y1, int x2, int y2) {
    return query(1, 1, 0, c - 1, 0, r - 1, y1, x1, y2, x2);
}

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 2310 ms 15288 KB Output is correct
5 Correct 1532 ms 15696 KB Output is correct
6 Correct 1762 ms 12580 KB Output is correct
7 Correct 2172 ms 12436 KB Output is correct
8 Correct 1081 ms 8008 KB Output is correct
9 Correct 1879 ms 12420 KB Output is correct
10 Correct 2032 ms 11944 KB Output is correct
11 Correct 1 ms 204 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 2 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 2 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 2 ms 204 KB Output is correct
12 Correct 4045 ms 23460 KB Output is correct
13 Correct 3870 ms 7448 KB Output is correct
14 Correct 1770 ms 948 KB Output is correct
15 Correct 4814 ms 11920 KB Output is correct
16 Correct 859 ms 27908 KB Output is correct
17 Correct 4070 ms 19036 KB Output is correct
18 Correct 7002 ms 29308 KB Output is correct
19 Correct 6021 ms 29424 KB Output is correct
20 Correct 6313 ms 28872 KB Output is correct
21 Correct 1 ms 204 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 2674 ms 15308 KB Output is correct
13 Correct 1605 ms 15720 KB Output is correct
14 Correct 1920 ms 12580 KB Output is correct
15 Correct 2077 ms 12220 KB Output is correct
16 Correct 1037 ms 7996 KB Output is correct
17 Correct 2037 ms 12452 KB Output is correct
18 Correct 2017 ms 12092 KB Output is correct
19 Correct 4075 ms 23436 KB Output is correct
20 Correct 3876 ms 7456 KB Output is correct
21 Correct 1771 ms 952 KB Output is correct
22 Correct 4859 ms 12052 KB Output is correct
23 Correct 739 ms 27892 KB Output is correct
24 Correct 4054 ms 18948 KB Output is correct
25 Correct 6972 ms 29332 KB Output is correct
26 Correct 6278 ms 29420 KB Output is correct
27 Correct 5580 ms 28900 KB Output is correct
28 Execution timed out 13077 ms 57800 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 2 ms 332 KB Output is correct
3 Correct 2 ms 332 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 2087 ms 15316 KB Output is correct
13 Correct 1493 ms 15600 KB Output is correct
14 Correct 1421 ms 12684 KB Output is correct
15 Correct 1865 ms 12452 KB Output is correct
16 Correct 884 ms 8040 KB Output is correct
17 Correct 1677 ms 12352 KB Output is correct
18 Correct 1838 ms 12156 KB Output is correct
19 Correct 4108 ms 23548 KB Output is correct
20 Correct 3858 ms 7340 KB Output is correct
21 Correct 1760 ms 1084 KB Output is correct
22 Correct 4855 ms 12208 KB Output is correct
23 Correct 785 ms 27940 KB Output is correct
24 Correct 4001 ms 18964 KB Output is correct
25 Correct 7027 ms 29324 KB Output is correct
26 Correct 5278 ms 29392 KB Output is correct
27 Correct 5160 ms 29008 KB Output is correct
28 Execution timed out 13061 ms 59036 KB Time limit exceeded
29 Halted 0 ms 0 KB -