oj.uz

Submission #620562

# Submission time Handle Problem Language Result Execution time Memory
620562 2022-08-03T07:09:13 Z MadokaMagicaFan Game (IOI13_game) C++14
100 / 100
 5776 ms 88268 KB 
#include "bits/stdc++.h"
#ifndef ONPC
#include <game.h>
#endif

using namespace std;

using ll = long long;
const ll inf = 1e9;

#define sz(v)                       ((int)v.size())
#define pb                          push_back

#define fst                         first
#define scn                         second
/* #define ONPC */

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int a, int b) { return a + rng()%(b-a+1); }

ll
gcd2(ll a, ll b)
{
    if (a == 0) return b;
    if (b == 0) return a;
    return gcd2(b, a%b);
}

struct treap{
    ll x, v;
    int s;
    int w;
    ll k;
    treap *l, *r;

    treap(ll _x, ll _k) {
        w = rand(0,10000);
        l = r = NULL;
        x = v = _x;
        k = _k;
        s = 1;
    }
};

using tp = treap*;

int size(tp x) { return (x == NULL ? 0 : x->s); }
ll xval(tp x) { return (x == NULL ? 0 : x->v); }

void
calc(tp x)
{
    if (x == NULL) return;
    x->s = 1 + size(x->l) + size(x->r);
    x->v = gcd2(x->x,gcd2(xval(x->l),xval(x->r)));
}

void 
split(tp t, tp& l, tp & r, ll k)
{
    if (t == NULL)
        l = r = NULL;
    else if (t->k > k)
        split(t->l, l, t->l, k), r = t;
    else
        split(t->r, t->r, r, k), l = t;
    calc(t);
}

void
unite(tp& t, tp l, tp r)
{
    if (l == NULL) t=r;
    else if (r == NULL) t=l;
    else if (l->w > r->w)
        unite(l->r,l->r,r), t = l;
    else
        unite(r->l,l,r->l), t = r;
    calc(t);
}


struct aint {
    int l, r;
    aint *la, *ra;
    tp v;

    aint(int _l, int _r)
        : l(_l), r(_r)
    {
        v = NULL;
        la = ra = NULL;
    }

    ll
    upd(int x, int y, ll val)
    {
        if (x < l || x > r) return getval(y,y);
        if (l == r)
            return set(y,val);

        if (!la) la = new aint(l, (l+r)>>1);
        if (!ra) ra = new aint(((l+r)>>1)+1, r);
        val = gcd2(la->upd(x,y,val), ra->upd(x,y,val));

        return set(y,val);
    }

    ll
    set(int y, ll val)
    {
        tp a, b, c;
        a = b = c = NULL;
        split(v, a, b, y-1);
        split(b, b, c, y);

        assert(size(b)<2);
        if (b == NULL)
            b = new treap(val, y);
        assert(b->k == y);
        b->x = val;
        calc(b);

        unite(v, a, b);
        unite(v, v, c);
        return val;
    }

    ll
    query(int lx, int rx, int ly, int ry)
    {
        if (rx < l || lx > r) return 0;
        if (lx <= l && r <= rx) return getval(ly,ry);

        ll ret = 0;
        if (la) ret = gcd2(ret, la->query(lx,rx,ly,ry));
        if (ra) ret = gcd2(ret, ra->query(lx,rx,ly,ry));
        return ret;
    }

    ll
    getval(int ly, int ry)
    {
        if (v == NULL) return 0;
        ll ret = 0;
        tp a, b, c;
        a = b = c = NULL;
        split(v, a, b, ly-1);
        split(b, b, c, ry);
        ret = xval(b);
        unite(v, a, b);
        unite(v, v, c);
        return ret;
    }
};

aint* root;

void
init(int R, int C)
{
    assert(R<=1e9);
    assert(C<=1e9);
    root = new aint(0,max(R,C)+100);
    return;
}

void
update(int p, int q, long long k)
{
    root->upd(p,q,k);
    return;
}

ll
calculate(int p, int q, int u, int v)
{
    /* if (p>u) swap(u,p); */
    /* if (q>v) swap(q,v); */
    return root->query(p, u, q, v);
}

#ifdef ONPC
void
solve()
{
    int r, c, q;
    cin >> r >> c >> q;
    init(r,c);

    int t, w, x, y;
    ll z;
    while(q--) {
        cin >> t;
        if (t == 1) {
            cin >> x >> y >> z;
            update(x,y,z);
        } else {
            cin >> w >> x >> y >> z;
            cout << calculate(w,x,y,z) << endl;
        }
    }
}

int32_t
main(int argc, char **argv)
{
    if (argc >= 2) {
        freopen(argv[1], "r", stdin);
    } else
        ios_base::sync_with_stdio(0);cin.tie(0);
    int t = 1;
    /* cin >> t; */
    while(t--)
        solve();
}
#endif

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1116 ms 19412 KB Output is correct
5 Correct 593 ms 19352 KB Output is correct
6 Correct 1447 ms 16652 KB Output is correct
7 Correct 1719 ms 16324 KB Output is correct
8 Correct 1059 ms 11284 KB Output is correct
9 Correct 1698 ms 16420 KB Output is correct
10 Correct 1486 ms 16244 KB Output is correct
11 Correct 1 ms 212 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 304 KB Output is correct
2 Correct 1 ms 308 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1253 ms 13316 KB Output is correct
13 Correct 2556 ms 7628 KB Output is correct
14 Correct 476 ms 5592 KB Output is correct
15 Correct 2912 ms 9020 KB Output is correct
16 Correct 842 ms 11424 KB Output is correct
17 Correct 1872 ms 9664 KB Output is correct
18 Correct 3415 ms 12872 KB Output is correct
19 Correct 2726 ms 12912 KB Output is correct
20 Correct 2567 ms 12372 KB Output is correct
21 Correct 1 ms 212 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 2 ms 300 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 2 ms 356 KB Output is correct
7 Correct 1 ms 304 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1245 ms 19436 KB Output is correct
13 Correct 572 ms 19240 KB Output is correct
14 Correct 1612 ms 16672 KB Output is correct
15 Correct 1896 ms 16344 KB Output is correct
16 Correct 1153 ms 11356 KB Output is correct
17 Correct 1801 ms 16628 KB Output is correct
18 Correct 1687 ms 16328 KB Output is correct
19 Correct 1223 ms 13356 KB Output is correct
20 Correct 2836 ms 7640 KB Output is correct
21 Correct 491 ms 5572 KB Output is correct
22 Correct 3045 ms 9072 KB Output is correct
23 Correct 1004 ms 11408 KB Output is correct
24 Correct 2023 ms 9684 KB Output is correct
25 Correct 3320 ms 12844 KB Output is correct
26 Correct 2748 ms 12976 KB Output is correct
27 Correct 2658 ms 12360 KB Output is correct
28 Correct 1188 ms 46396 KB Output is correct
29 Correct 2390 ms 49112 KB Output is correct
30 Correct 4305 ms 33848 KB Output is correct
31 Correct 3901 ms 27608 KB Output is correct
32 Correct 541 ms 10124 KB Output is correct
33 Correct 1042 ms 10520 KB Output is correct
34 Correct 1679 ms 42832 KB Output is correct
35 Correct 2602 ms 29068 KB Output is correct
36 Correct 4765 ms 46996 KB Output is correct
37 Correct 3617 ms 47152 KB Output is correct
38 Correct 3341 ms 46588 KB Output is correct
39 Correct 3195 ms 38752 KB Output is correct
40 Correct 1 ms 212 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 2 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 212 KB Output is correct
6 Correct 1 ms 308 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 2 ms 340 KB Output is correct
10 Correct 1 ms 308 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1192 ms 19460 KB Output is correct
13 Correct 659 ms 19152 KB Output is correct
14 Correct 1676 ms 16704 KB Output is correct
15 Correct 1919 ms 16360 KB Output is correct
16 Correct 1068 ms 11268 KB Output is correct
17 Correct 1859 ms 16416 KB Output is correct
18 Correct 1527 ms 16172 KB Output is correct
19 Correct 1240 ms 13556 KB Output is correct
20 Correct 2518 ms 7652 KB Output is correct
21 Correct 431 ms 5488 KB Output is correct
22 Correct 3094 ms 9100 KB Output is correct
23 Correct 1092 ms 11504 KB Output is correct
24 Correct 1868 ms 9756 KB Output is correct
25 Correct 3519 ms 12796 KB Output is correct
26 Correct 2793 ms 12960 KB Output is correct
27 Correct 2526 ms 12348 KB Output is correct
28 Correct 1113 ms 46408 KB Output is correct
29 Correct 2238 ms 49076 KB Output is correct
30 Correct 3788 ms 33888 KB Output is correct
31 Correct 3253 ms 27704 KB Output is correct
32 Correct 635 ms 10124 KB Output is correct
33 Correct 955 ms 10596 KB Output is correct
34 Correct 1704 ms 42832 KB Output is correct
35 Correct 2211 ms 29148 KB Output is correct
36 Correct 4438 ms 46972 KB Output is correct
37 Correct 3572 ms 47100 KB Output is correct
38 Correct 3367 ms 46588 KB Output is correct
39 Correct 1670 ms 86296 KB Output is correct
40 Correct 3523 ms 88268 KB Output is correct
41 Correct 5762 ms 63568 KB Output is correct
42 Correct 5313 ms 49896 KB Output is correct
43 Correct 2243 ms 83080 KB Output is correct
44 Correct 782 ms 10620 KB Output is correct
45 Correct 2730 ms 38696 KB Output is correct
46 Correct 5776 ms 87208 KB Output is correct
47 Correct 5662 ms 87116 KB Output is correct
48 Correct 5528 ms 86664 KB Output is correct
49 Correct 1 ms 212 KB Output is correct