oj.uz

Submission #416704

# Submission time Handle Problem Language Result Execution time Memory
416704 2021-06-02T20:17:35 Z Tangent Game (IOI13_game) C++17
37 / 100
 13000 ms 31264 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;
}

int r, c;
map<pii, ll> t;

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

void sett(int y, int x, ll v) {
    if (v) {
        t[{y, x}] = v;
    } else {
        t.erase({y, x});
    }
    // 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 4 ms 460 KB Output is correct
3 Correct 4 ms 460 KB Output is correct
4 Correct 1 ms 292 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 2 ms 332 KB Output is correct
11 Correct 2 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 296 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 4877 ms 25344 KB Output is correct
5 Correct 3733 ms 25208 KB Output is correct
6 Correct 3224 ms 23088 KB Output is correct
7 Correct 3940 ms 22668 KB Output is correct
8 Correct 1964 ms 15624 KB Output is correct
9 Correct 3746 ms 22808 KB Output is correct
10 Correct 3824 ms 22404 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 4 ms 460 KB Output is correct
3 Correct 4 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 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 2 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 11957 ms 31228 KB Output is correct
13 Execution timed out 13099 ms 14936 KB Time limit exceeded
14 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 4 ms 460 KB Output is correct
3 Correct 4 ms 460 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 292 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 2 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 4890 ms 25396 KB Output is correct
13 Correct 3760 ms 25440 KB Output is correct
14 Correct 3193 ms 22880 KB Output is correct
15 Correct 3926 ms 22996 KB Output is correct
16 Correct 2051 ms 15628 KB Output is correct
17 Correct 3750 ms 23052 KB Output is correct
18 Correct 3957 ms 22352 KB Output is correct
19 Correct 11995 ms 31188 KB Output is correct
20 Execution timed out 13010 ms 14844 KB Time limit exceeded
21 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 4 ms 460 KB Output is correct
3 Correct 4 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 292 KB Output is correct
8 Correct 1 ms 288 KB Output is correct
9 Correct 3 ms 460 KB Output is correct
10 Correct 2 ms 332 KB Output is correct
11 Correct 2 ms 332 KB Output is correct
12 Correct 4887 ms 25404 KB Output is correct
13 Correct 3766 ms 25140 KB Output is correct
14 Correct 3182 ms 22988 KB Output is correct
15 Correct 3841 ms 22620 KB Output is correct
16 Correct 1996 ms 15616 KB Output is correct
17 Correct 3736 ms 22832 KB Output is correct
18 Correct 4094 ms 22432 KB Output is correct
19 Correct 12047 ms 31264 KB Output is correct
20 Execution timed out 13072 ms 14916 KB Time limit exceeded
21 Halted 0 ms 0 KB -