oj.uz

Submission #416718

# Submission time Handle Problem Language Result Execution time Memory
416718 2021-06-02T20:33:34 Z Tangent Game (IOI13_game) C++17
37 / 100
 13000 ms 27160 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;
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 3 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 3 ms 460 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 0 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 4244 ms 21096 KB Output is correct
5 Correct 3116 ms 21276 KB Output is correct
6 Correct 3005 ms 18536 KB Output is correct
7 Correct 3823 ms 18056 KB Output is correct
8 Correct 1827 ms 11400 KB Output is correct
9 Correct 3546 ms 18320 KB Output is correct
10 Correct 3646 ms 17836 KB Output is correct
11 Correct 1 ms 204 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 4 ms 460 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 3 ms 460 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 10396 ms 27108 KB Output is correct
13 Correct 11898 ms 11132 KB Output is correct
14 Correct 2393 ms 5732 KB Output is correct
15 Execution timed out 13084 ms 19548 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 3 ms 460 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 4240 ms 20912 KB Output is correct
13 Correct 3117 ms 21188 KB Output is correct
14 Correct 2989 ms 18348 KB Output is correct
15 Correct 3559 ms 18028 KB Output is correct
16 Correct 1796 ms 11356 KB Output is correct
17 Correct 3525 ms 18132 KB Output is correct
18 Correct 3744 ms 17764 KB Output is correct
19 Correct 10596 ms 27084 KB Output is correct
20 Correct 11981 ms 11264 KB Output is correct
21 Correct 2395 ms 5764 KB Output is correct
22 Execution timed out 13083 ms 19420 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 3 ms 460 KB Output is correct
3 Correct 3 ms 460 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 3 ms 460 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 4 ms 460 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 4302 ms 20980 KB Output is correct
13 Correct 3137 ms 21188 KB Output is correct
14 Correct 3124 ms 18340 KB Output is correct
15 Correct 4069 ms 17960 KB Output is correct
16 Correct 1950 ms 11408 KB Output is correct
17 Correct 3740 ms 18152 KB Output is correct
18 Correct 3810 ms 17764 KB Output is correct
19 Correct 10590 ms 27160 KB Output is correct
20 Correct 11939 ms 11236 KB Output is correct
21 Correct 2440 ms 5760 KB Output is correct
22 Execution timed out 13052 ms 19308 KB Time limit exceeded
23 Halted 0 ms 0 KB -