oj.uz

Submission #426813

# Submission time Handle Problem Language Result Execution time Memory
426813 2021-06-14T10:07:26 Z Aldas25 Game (IOI13_game) C++14
63 / 100
 3793 ms 256004 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define REP(n) FOR(O, 1, (n))
#define f first
#define s second
#define pb push_back
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<pii> vii;
typedef long long ll;
typedef vector<ll> vl;

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 segtree1 {
    struct node1 {
        ll fr, to;
        ll val;
        node1 * leCh;
        node1 * riCh;

        node1 (ll _fr, ll _to) {
            fr = _fr;
            to = _to;
            val = 0;
            leCh = riCh = nullptr;
        }

        void upd () {
            ll mid = (fr+to)/2;
            if (!leCh)
                leCh = new node1 (fr, mid);
            if (!riCh)
                riCh = new node1 (mid+1, to);
        }
    };

    void upd (ll p, ll newVal, node1 * cur) {
        if (cur->fr == cur->to){
            cur->val = newVal;
            return;
        }
        ll mid = (cur->fr) + (cur->to);
        mid /= 2;
        cur->upd();
        if (p <= mid)
            upd(p, newVal, cur->leCh);
        else
            upd (p, newVal, cur->riCh);

        cur->val = gcd2(cur->leCh->val, cur->riCh->val);
    }

    ll get(ll rfr, ll rto, node1 * cur) {
        if (rfr > (cur->to) || rto < (cur->fr)) return 0;
        if (rfr <= (cur->fr) && (cur->to) <= rto) return cur->val;
        if (!(cur->leCh)) return 0;
        cur->upd();
        return gcd2(get(rfr, rto, cur->leCh), get(rfr, rto, cur->riCh));
    }

    node1 * root = new node1 (0, 1e9);

    void upd (ll pos, ll newVal) {
        upd(pos, newVal, root);
    }

    ll get (ll fr, ll to) {
        return get(fr, to, root);
    }

};

struct segtree2 {
    struct node2 {
        ll fr, to;
        segtree1 * tr;
        node2 * leCh;
        node2 * riCh;

        node2 (ll _fr, ll _to) {
            fr = _fr;
            to = _to;
            tr = new segtree1();
            leCh = riCh = nullptr;
        }

        void upd () {
            ll mid = (fr+to)/2;
            if (!leCh)
                leCh = new node2 (fr, mid);
            if (!riCh)
                riCh = new node2 (mid+1, to);
        }
    };

    ll get(ll frx, ll tox, ll fry, ll toy, node2 * cur) {
        if (frx > (cur->to) || tox < (cur->fr)) {
          //  cout << " in get, discard frx = " << frx << " tox = " << tox << "fry = " << fry
          //<< " toy = " << toy << " cur: [" << cur->fr << ", " << cur->to << "]" << endl;
            return 0;
        }
        if (frx <= (cur->fr) && (cur->to) <= tox) {
            ll ret = cur->tr->get(fry, toy);
        //    cout << " in get, frx = " << frx << " tox = " << tox << "fry = " << fry
         // << " toy = " << toy << " cur: [" << cur->fr << ", " << cur->to << "]" << endl;
           // cout << "    returnin ret = " << ret << endl;
            return ret;
        }
        if (!(cur->leCh)) return 0;
        //cur->upd();
        ll ret = gcd2(get(frx, tox, fry, toy, cur->leCh), get(frx, tox, fry, toy, cur->riCh));
       // cout << " in get, frx = " << frx << " tox = " << tox << "fry = " << fry
        //  << " toy = " << toy << " cur: [" << cur->fr << ", " << cur->to << "]" << endl;
        //cout << "     returning ret = " << ret << endl;
        return ret;
    }

    void upd (ll px, ll py, ll newVal, node2 * cur) {
        if (cur->fr == cur->to){
           // cout << " in upd, cur [" << cur->fr << ", " << cur->to << "], py = " << py << " newVal = " << newVal << endl;
            cur->tr->upd(py, newVal);
            return;
        }
        ll mid = (cur->fr) + (cur->to);
        mid /= 2;
        cur->upd();
        if (px <= mid)
            upd(px, py, newVal, cur->leCh);
        else
            upd (px, py, newVal, cur->riCh);

       // cur->val = gcd2(cur->leCh->val, cur->riCh->val);
        ll g = gcd2(get(cur->fr, mid, py, py, cur->leCh), get(mid+1, cur->to, py, py, cur->riCh));
        cur->tr->upd (py, g);
//        cout << " in upd, cur [" << cur->fr << ", " << cur->to << "], py = " << py << " g = " << g << endl;
    }

    node2 * root = new node2 (0, 1e9);

    void upd (ll posx, ll posy, ll newVal) {
        upd(posx, posy, newVal, root);
    }

    ll get (ll frx, ll fry, ll tox, ll toy) {
        return get(frx, fry, tox, toy, root);
    }
};

segtree2 tree;

void init(int R, int C) {

}

void update(int P, int Q, long long K) {
    tree.upd(P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    //cout << "------------------doing get" << endl;
    ll ans = tree.get(P, U, Q, V);
    //cout << "---------------------after get" << endl;
    return ans;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1226 ms 114460 KB Output is correct
5 Correct 952 ms 114184 KB Output is correct
6 Correct 1315 ms 111812 KB Output is correct
7 Correct 1463 ms 111576 KB Output is correct
8 Correct 891 ms 69008 KB Output is correct
9 Correct 1421 ms 112520 KB Output is correct
10 Correct 1336 ms 111520 KB Output is correct
11 Correct 1 ms 332 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 4 ms 1148 KB Output is correct
3 Correct 4 ms 1100 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 3 ms 1100 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 3 ms 1100 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 2 ms 588 KB Output is correct
12 Correct 1647 ms 40612 KB Output is correct
13 Correct 2011 ms 22928 KB Output is correct
14 Correct 677 ms 6572 KB Output is correct
15 Correct 2288 ms 34688 KB Output is correct
16 Correct 826 ms 59828 KB Output is correct
17 Correct 2236 ms 42620 KB Output is correct
18 Correct 3716 ms 61080 KB Output is correct
19 Correct 3379 ms 61272 KB Output is correct
20 Correct 3181 ms 60632 KB Output is correct
21 Correct 1 ms 332 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 4 ms 1100 KB Output is correct
3 Correct 4 ms 1100 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 3 ms 1100 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 4 ms 1100 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 2 ms 588 KB Output is correct
12 Correct 1228 ms 114312 KB Output is correct
13 Correct 933 ms 114236 KB Output is correct
14 Correct 1325 ms 111708 KB Output is correct
15 Correct 1524 ms 111544 KB Output is correct
16 Correct 1010 ms 68928 KB Output is correct
17 Correct 1410 ms 112404 KB Output is correct
18 Correct 1303 ms 111596 KB Output is correct
19 Correct 1642 ms 40768 KB Output is correct
20 Correct 1977 ms 22820 KB Output is correct
21 Correct 678 ms 6272 KB Output is correct
22 Correct 2283 ms 34716 KB Output is correct
23 Correct 973 ms 59752 KB Output is correct
24 Correct 2449 ms 42524 KB Output is correct
25 Correct 3793 ms 61032 KB Output is correct
26 Correct 3017 ms 61240 KB Output is correct
27 Correct 3127 ms 60488 KB Output is correct
28 Runtime error 496 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 4 ms 1100 KB Output is correct
3 Correct 5 ms 1100 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 3 ms 1100 KB Output is correct
7 Correct 1 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 3 ms 1100 KB Output is correct
10 Correct 2 ms 716 KB Output is correct
11 Correct 3 ms 588 KB Output is correct
12 Correct 1333 ms 114284 KB Output is correct
13 Correct 1008 ms 114160 KB Output is correct
14 Correct 1297 ms 111740 KB Output is correct
15 Correct 1446 ms 111552 KB Output is correct
16 Correct 802 ms 68968 KB Output is correct
17 Correct 1342 ms 112448 KB Output is correct
18 Correct 1405 ms 111480 KB Output is correct
19 Correct 1713 ms 40620 KB Output is correct
20 Correct 2113 ms 22692 KB Output is correct
21 Correct 724 ms 6288 KB Output is correct
22 Correct 2334 ms 34560 KB Output is correct
23 Correct 847 ms 59756 KB Output is correct
24 Correct 2179 ms 42440 KB Output is correct
25 Correct 3390 ms 61032 KB Output is correct
26 Correct 3103 ms 61428 KB Output is correct
27 Correct 3025 ms 60636 KB Output is correct
28 Runtime error 452 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -