oj.uz

Submission #1088474

# Submission time Handle Problem Language Result Execution time Memory
1088474 2024-09-14T13:27:34 Z makrav Game (IOI13_game) C++17
10 / 100
 13000 ms 4852 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;
using ll = long long;

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()
#define int ll

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;
}

// struct pair<int, int> {
//     int x, y;
// };

bool operator<(pair<int, int> x, pair<int, int> y) {
    return (x.second == y.second ? x.first < y.first : x.second < y.second);
}

bool operator==(pair<int, int> x, pair<int, int> y) {
    return x.first == y.first && x.second == y.second;
}

bool operator>(pair<int, int> x, pair<int, int> y) {
    if (x == y) return false;
    return !(x < y);
}

bool compare(pair<int, int> x, pair<int, int> y) {
    return (x.first == y.first ? x.second < y.second : x.first < y.first);
}

bool cmp(pair<pair<int, int>, int> c1, pair<pair<int, int>, int> c2) {
	if (c1.first == c2.first) return c1.second < c2.second;
	return compare(c1.first, c2.first);
}

struct segtree {
    int n;
    vector<int> a;
    vector<pair<int, int>> C;
    vector<int> t;
    segtree() = default;
    segtree(int n_, vector<pair<pair<int, int>, int>> A) {
        n = n_;
        a.resize(n); C.resize(n);
        for (int i = 0; i < n; i++) {
            C[i] = A[i].first; a[i] = A[i].second;
        }
        t.assign(4 * n, 0);
        build(1, 0, n);
    }  

    void build(int v, int tl, int tr) {
        if (tl + 1 == tr) {
            t[v] = a[tl];
            return;
        }
        int tm = (tl + tr) / 2;
        build(v * 2, tl, tm); build(v * 2 + 1, tm, tr);
        t[v] = gcd(t[v * 2], t[v * 2 + 1]);
    }

    void upd(int v, int tl, int tr, pair<int, int> &c, int newval) {
        if (tl + 1 == tr) {
            t[v] = newval;
            return;
        }
        int tm = (tl + tr) / 2;
        if (C[tm - 1] < c) upd(v * 2 + 1, tm, tr, c, newval);
        else upd(v * 2, tl, tm, c, newval);
        t[v] = gcd(t[v * 2], t[v * 2 + 1]);
    }

    int get(int v, int tl, int tr, int y1, int y2) {
        if (y1 <= C[tl].second && C[tr - 1].second <= y2) return t[v];
        if (C[tl].second > y2 || C[tr - 1].second < y1) return 0;
        int tm = (tl + tr) / 2;
        return gcd(get(v*2,tl,tm,y1,y2), get(v*2+1,tm,tr,y1,y2));
    }
};

struct merge_sort_tree {
    int n;
    vector<pair<pair<int, int>, int>> xd;
    vector<segtree> sg;
    vector<vector<pair<pair<int, int>, int>>> tree;
    merge_sort_tree() = default;
    merge_sort_tree(int n_, vector<pair<pair<int, int>, int>> &xd_) {
        xd =xd_;
        sort(all(xd), cmp);
        n = n_;
        tree.resize(4 * n);
        sg.resize(4 * n);
        build(1, 0, n);
    }

    void build(int v, int tl, int tr) {
        if (tl + 1 == tr) {
            tree[v] = {xd[tl]};
            sg[v] = segtree(tr - tl, tree[v]);
            return;
        }
        int tm = (tl + tr) / 2;
        build(v * 2, tl, tm); build(v * 2 + 1, tm, tr);
        tree[v].resize(tr - tl);
        merge(all(tree[v * 2]), all(tree[v * 2 + 1]), tree[v].begin());
        sg[v] = segtree(tr - tl, tree[v]);
    }

    void update_value(int v, int tl, int tr, pair<int, int> x, int value) {
        sg[v].upd(1, 0, tr - tl, x, value);
        if (tl + 1 == tr) return;
        int tm = (tl + tr) / 2;
        if (compare(xd[tm - 1].first, x)) update_value(v * 2 + 1, tm, tr, x, value);
        else update_value(v * 2, tl, tm, x, value);
    }

    int getans(int v, int tl, int tr, int xl, int xr, int yl, int yr) {
        if (xl > xd[tr - 1].first.first || xr < xd[tl].first.first) return 0;
        if (xl <= xd[tl].first.first && xd[tr - 1].first.first <= xr) {
            return sg[v].get(1, 0, tr - tl, yl, yr);
        }
        int tm = (tl + tr) / 2;
        return gcd(getans(v * 2, tl, tm, xl, xr, yl, yr), getans(v * 2 + 1, tm, tr, xl, xr, yl, yr));
    }
};

map<pair<int, int>, int> value, firocc;
const int K = 1000000000;
int curind_query = 0, lol = -1;
vector<pair<int, int>> ahaha;
merge_sort_tree mst;
int mst_size = 0;

void init(int32_t R, int32_t C) {
    /* ... */
}

void update(int32_t P, int32_t Q, long long kk) {
    // curind_query++;
    // if (firocc.find({P, Q}) == firocc.end()) {
    //     firocc[{P, Q}] = curind_query;
    // }
    value[{P, Q}] = kk;
    ahaha.pb({P, Q});
    return;
    if (curind_query % K == 0) {
        vector<pair<pair<int, int>, int>> to_mst;
        for (auto &u : value) to_mst.pb(u);
        mst_size = sz(to_mst);
        mst = merge_sort_tree(mst_size, to_mst);
        ahaha.clear();
    } else {
        if (firocc[{P, Q}] <= curind_query - curind_query % K) {
            mst.update_value(1, 0, mst_size, {P, Q}, kk);
        } else {
            ahaha.pb({P, Q});
        }
    }
}

long long calculate(int32_t P, int32_t Q, int32_t U, int32_t V) {
    int ans1 = 0; //(mst_size == 0 ? 0 : mst.getans(1, 0, mst_size, P, U, Q, V));
    for (auto &u : ahaha) {
        if (P <= u.first && u.first <= U && Q <= u.second && u.second <= V) {
            ans1 = gcd2(ans1, value[u]);
        }
    }
    return ans1;
}

#ifdef LOCAL 
    signed main() {
        freopen("in.txt", "r", stdin);
        freopen("out.txt", "w", stdout);
        int r, c, n; cin >> r >> c >> n;
        init(r, c);
        for (int i = 0; i < n; i++) {
            int t; cin >> t;
            if (t == 1) {
                int p, q, k; cin >> p >> q >> k; update(p, q, k);
            } else {
                int p, q, u, v; cin >> p >> q >> u >> v;
                cout << calculate(p, q, u, v) << '\n';
            }
        }
    }
#endif

Subtask #1
10.0 / 10.0

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

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Execution timed out 13093 ms 4836 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Execution timed out 13089 ms 4628 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Execution timed out 13057 ms 4692 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Execution timed out 13069 ms 4852 KB Time limit exceeded
13 Halted 0 ms 0 KB -