oj.uz

Submission #659304

# Submission time Handle Problem Language Result Execution time Memory
659304 2022-11-17T10:45:58 Z Danilo21 Game (IOI13_game) C++17
80 / 100
 3409 ms 162104 KB 
        #include <bits/stdc++.h>
        #include "game.h"

        #define ll long long
        #define ld long double
        #define pb push_back
        #define fi first
        #define se second
        #define en '\n'
        #define sp ' '
        #define tb '\t'
        #define ri(n) int n; cin >> n
        #define rl(n) ll n; cin >> n
        #define rs(s) string s; cin >> s
        #define rc(c) char c; cin >> c
        #define rv(v) for (auto &x : v) cin >> x
        #define pven(v) for (auto x : v) cout << x << en
        #define pv(v) for (auto x : v) cout << x << sp; cout << en
        #define all(v) v.begin(), v.end()
        #define rall(v) v.rbegin(), v.rend()
        #define yes cout << "YES" << en
        #define no cout << "NO" << en
        #define smin(a, b) a = min(a, b)
        #define smax(a, b) a = max(a, b)
        #define ssort(a, b) if (a < b) swap(a, b)
        #define bitcnt(a) (__builtin_popcountll(a))
        #define bithigh(a) (63-__builtin_clzll(a))
        #define lg bithigh
        #define highpow(a) (1LL << (ll)lg(a))

        using namespace std;

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

        const ll LINF = 4e18;
        const int mxN = 1e7+10, mxM = 5e5, INF = 2e9;
        ll n, m, node[mxN];
        int root2D, N[2], root[mxM], ch[mxN][2], ch2[mxM][2];

        int Node(){ return N[0]++; }

        int Root(){ root[N[1]] = Node(); return N[1]++; }

        int Child(int s, int i){ if (!~s) return -1; if (!~ch[s][i]) ch[s][i] = Node(); return ch[s][i]; }

        int _Child(int s, int i){ if (!~s) return -1; return ch[s][i]; }

        int Child2(int s, int i){ if (!~s) return -1; if (!~ch2[s][i]) ch2[s][i] = Root(); return ch2[s][i]; }

        ll Val(int s){ return (~s ? node[s] : 0); }

        void Print(int s, ll l, ll r){
            if (!~s) return;
            cout << tb << tb << s << sp << l << sp << r << sp << node[s] << en;
            ll m = (l + r)>>1;
            Print(ch[s][0], l, m);
            Print(ch[s][1], m+1, r);
        }
        void Print(int s){ cout << tb << "SEGTREE\n"; Print(s, 0, m-1); cout << en; }

        void Print2D(int s, ll l, ll r){
            if (!~s) return;
            cout << tb << l << sp << r << en;
            Print(root[s]);
            ll m = (l + r)>>1;
            Print2D(ch2[s][0], l, m);
            Print2D(ch2[s][1], m+1, r);
        }
        void Print2D(){ cout << "2D SEGTREE\n"; Print2D(root2D, 0, n-1); cout << en; }

        void update(int s, ll l, ll r, ll pos, ll x){
            if (l == r){ node[s] = x; return; }
            ll m = (l + r)>>1;
            if (pos <= m) update(Child(s, 0), l, m, pos, x);
            else update(Child(s, 1), m+1, r, pos, x);
            node[s] = gcd2(Val(ch[s][0]), Val(ch[s][1]));
        }
        void update(int s, ll pos, ll x){ update(s, 0, m-1, pos, x); }

        ll query(int s, ll l, ll r, ll ql, ll qr){
            if (l > qr || r < ql || !~s) return 0;
            if (l >= ql && r <= qr) return node[s];
            ll m = (l + r)>>1;
            ll a = query(ch[s][0], l, m, ql, qr);
            ll b = query(ch[s][1], m+1, r, ql, qr);
            return gcd2(a, b);
        }
        ll query(int s, ll l, ll r){ return query(s, 0, m-1, l, r); }

        void update2D(int s, ll l, ll r, ll pos, array<ll, 2> args){
            if (l == r){ update(root[s], args[0], args[1]); return; }
            ll m = (l + r)>>1;
            if (pos <= m) update2D(Child2(s, 0), l, m, pos, args);
            else update2D(Child2(s, 1), m+1, r, pos, args);
            ll x = (~ch2[s][0] ? query(root[ch2[s][0]], args[0], args[0]) : 0);
            ll y = (~ch2[s][1] ? query(root[ch2[s][1]], args[0], args[0]) : 0);
            update(root[s], args[0], gcd2(x, y));
        }
        void update2D(ll i, ll j, ll x){ update2D(root2D, 0, n-1, i, {j, x}); }

        ll query2D(int s, ll l, ll r, ll ql, ll qr, array<ll, 2> args){
            if (l > qr || r < ql || !~s) return 0;
            if (l >= ql && r <= qr) return query(root[s], args[0], args[1]);
            ll m = (l + r)>>1;
            ll a = query2D(ch2[s][0], l, m, ql, qr, args);
            ll b = query2D(ch2[s][1], m+1, r, ql, qr, args);
            return gcd2(a, b);
        }
        ll query2D(ll l1, ll r1, ll l2, ll r2){ return query2D(root2D, 0, n-1, l1, r1, {l2, r2}); }

        void init(int R, int C){
            memset(ch, -1, sizeof(ch));
            memset(ch2, -1, sizeof(ch2));
            n = highpow(R);
            if (bitcnt(R) > 1) n <<= 1;
            m = highpow(C);
            if (bitcnt(C) > 1) m <<= 1;
            root2D = Root();
        }

        void update(int P, int Q, long long K) {
            update2D(P, Q, K);
        }

        long long calculate(int P, int Q, int U, int V) {
            return query2D(P, U, Q, V);
        }

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 82408 KB Output is correct
2 Correct 33 ms 82536 KB Output is correct
3 Correct 32 ms 82524 KB Output is correct
4 Correct 32 ms 82448 KB Output is correct
5 Correct 32 ms 82396 KB Output is correct
6 Correct 35 ms 82496 KB Output is correct
7 Correct 39 ms 82404 KB Output is correct
8 Correct 33 ms 82388 KB Output is correct
9 Correct 33 ms 82436 KB Output is correct
10 Correct 32 ms 82520 KB Output is correct
11 Correct 33 ms 82384 KB Output is correct
12 Correct 38 ms 82476 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 82480 KB Output is correct
2 Correct 32 ms 82380 KB Output is correct
3 Correct 32 ms 82424 KB Output is correct
4 Correct 445 ms 88836 KB Output is correct
5 Correct 327 ms 89044 KB Output is correct
6 Correct 413 ms 86008 KB Output is correct
7 Correct 444 ms 85656 KB Output is correct
8 Correct 327 ms 85452 KB Output is correct
9 Correct 434 ms 85772 KB Output is correct
10 Correct 400 ms 85324 KB Output is correct
11 Correct 33 ms 82464 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 82400 KB Output is correct
2 Correct 37 ms 82408 KB Output is correct
3 Correct 38 ms 82504 KB Output is correct
4 Correct 38 ms 82392 KB Output is correct
5 Correct 32 ms 82412 KB Output is correct
6 Correct 32 ms 82516 KB Output is correct
7 Correct 33 ms 82404 KB Output is correct
8 Correct 34 ms 82388 KB Output is correct
9 Correct 33 ms 82432 KB Output is correct
10 Correct 33 ms 82452 KB Output is correct
11 Correct 33 ms 82408 KB Output is correct
12 Correct 732 ms 89372 KB Output is correct
13 Correct 1207 ms 84564 KB Output is correct
14 Correct 289 ms 83180 KB Output is correct
15 Correct 1373 ms 85308 KB Output is correct
16 Correct 302 ms 87516 KB Output is correct
17 Correct 641 ms 86220 KB Output is correct
18 Correct 1002 ms 88072 KB Output is correct
19 Correct 866 ms 87984 KB Output is correct
20 Correct 825 ms 87460 KB Output is correct
21 Correct 34 ms 82448 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 82384 KB Output is correct
2 Correct 32 ms 82520 KB Output is correct
3 Correct 32 ms 82516 KB Output is correct
4 Correct 33 ms 82492 KB Output is correct
5 Correct 33 ms 82384 KB Output is correct
6 Correct 35 ms 82636 KB Output is correct
7 Correct 32 ms 82444 KB Output is correct
8 Correct 34 ms 82492 KB Output is correct
9 Correct 32 ms 82504 KB Output is correct
10 Correct 32 ms 82408 KB Output is correct
11 Correct 32 ms 82380 KB Output is correct
12 Correct 439 ms 88884 KB Output is correct
13 Correct 342 ms 89040 KB Output is correct
14 Correct 421 ms 85952 KB Output is correct
15 Correct 440 ms 85580 KB Output is correct
16 Correct 327 ms 85444 KB Output is correct
17 Correct 426 ms 85700 KB Output is correct
18 Correct 418 ms 85276 KB Output is correct
19 Correct 743 ms 89560 KB Output is correct
20 Correct 1196 ms 84540 KB Output is correct
21 Correct 289 ms 83140 KB Output is correct
22 Correct 1371 ms 85156 KB Output is correct
23 Correct 308 ms 87472 KB Output is correct
24 Correct 638 ms 86164 KB Output is correct
25 Correct 1012 ms 87752 KB Output is correct
26 Correct 874 ms 88140 KB Output is correct
27 Correct 835 ms 87512 KB Output is correct
28 Correct 614 ms 145148 KB Output is correct
29 Correct 1490 ms 154476 KB Output is correct
30 Correct 3409 ms 133420 KB Output is correct
31 Correct 3405 ms 121752 KB Output is correct
32 Correct 546 ms 83148 KB Output is correct
33 Correct 689 ms 83752 KB Output is correct
34 Correct 696 ms 151488 KB Output is correct
35 Correct 1060 ms 118060 KB Output is correct
36 Correct 2153 ms 151820 KB Output is correct
37 Correct 1681 ms 151876 KB Output is correct
38 Correct 1653 ms 151368 KB Output is correct
39 Correct 1390 ms 135900 KB Output is correct
40 Correct 33 ms 82508 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 82468 KB Output is correct
2 Correct 33 ms 82500 KB Output is correct
3 Correct 32 ms 82480 KB Output is correct
4 Correct 33 ms 82428 KB Output is correct
5 Correct 41 ms 82464 KB Output is correct
6 Correct 33 ms 82432 KB Output is correct
7 Correct 36 ms 82476 KB Output is correct
8 Correct 35 ms 82456 KB Output is correct
9 Correct 33 ms 82476 KB Output is correct
10 Correct 33 ms 82380 KB Output is correct
11 Correct 33 ms 82508 KB Output is correct
12 Correct 437 ms 88744 KB Output is correct
13 Correct 327 ms 89100 KB Output is correct
14 Correct 418 ms 85924 KB Output is correct
15 Correct 450 ms 85640 KB Output is correct
16 Correct 326 ms 85452 KB Output is correct
17 Correct 430 ms 85656 KB Output is correct
18 Correct 407 ms 85312 KB Output is correct
19 Correct 733 ms 89412 KB Output is correct
20 Correct 1185 ms 84528 KB Output is correct
21 Correct 290 ms 83152 KB Output is correct
22 Correct 1377 ms 85196 KB Output is correct
23 Correct 306 ms 87512 KB Output is correct
24 Correct 650 ms 86308 KB Output is correct
25 Correct 1041 ms 87992 KB Output is correct
26 Correct 874 ms 88028 KB Output is correct
27 Correct 831 ms 87400 KB Output is correct
28 Correct 616 ms 145100 KB Output is correct
29 Correct 1487 ms 154320 KB Output is correct
30 Correct 3409 ms 133328 KB Output is correct
31 Correct 3358 ms 121776 KB Output is correct
32 Correct 537 ms 83136 KB Output is correct
33 Correct 671 ms 83748 KB Output is correct
34 Correct 687 ms 151464 KB Output is correct
35 Correct 1125 ms 118032 KB Output is correct
36 Correct 2017 ms 151724 KB Output is correct
37 Correct 1730 ms 152052 KB Output is correct
38 Correct 1639 ms 151396 KB Output is correct
39 Incorrect 526 ms 162104 KB Output isn't correct
40 Halted 0 ms 0 KB -