oj.uz

Submission #659262

# Submission time Handle Problem Language Result Execution time Memory
659262 2022-11-17T07:56:48 Z Danilo21 Game (IOI13_game) C++17
80 / 100
 3674 ms 256000 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 = 2e7+10, INF = 2e9;
ll n, m, node[mxN];
int root2D, N, ch[mxN][2];

int Node(){ return N++; }

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

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

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

int _Child(int s, int i){ if (!~s) return -1; return ch[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, n-1); cout << en; }

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

void update2D(int s, ll l, ll r, ll pos, array<ll, 2> args){
    if (l == r){ update(node[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 = (~ch[s][0] ? query(node[ch[s][0]], args[0], args[0]) : 0);
    ll y = (~ch[s][1] ? query(node[ch[s][1]], args[0], args[0]) : 0);
    update(node[s], args[0], gcd2(x, y));
}
void update2D(ll i, ll j, ll x){ update2D(root2D, 0, m-1, j, {i, 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(node[s], args[0], args[1]);
    ll m = (l + r)>>1;
    ll a = query2D(ch[s][0], l, m, ql, qr, args);
    ll b = query2D(ch[s][1], m+1, r, ql, qr, args);
    return gcd2(a, b);
}
ll query2D(ll i1, ll j1, ll i2, ll j2){ return query2D(root2D, 0, m-1, j1, j2, {i1, i2}); }

void init(int R, int C){
    memset(ch, -1, sizeof(ch));
    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, Q, U, V);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 156748 KB Output is correct
2 Correct 61 ms 156884 KB Output is correct
3 Correct 57 ms 156776 KB Output is correct
4 Correct 57 ms 156748 KB Output is correct
5 Correct 57 ms 156776 KB Output is correct
6 Correct 59 ms 156868 KB Output is correct
7 Correct 59 ms 156748 KB Output is correct
8 Correct 58 ms 156844 KB Output is correct
9 Correct 69 ms 156840 KB Output is correct
10 Correct 58 ms 156800 KB Output is correct
11 Correct 63 ms 156916 KB Output is correct
12 Correct 55 ms 156836 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 156772 KB Output is correct
2 Correct 60 ms 156748 KB Output is correct
3 Correct 65 ms 156748 KB Output is correct
4 Correct 516 ms 164144 KB Output is correct
5 Correct 457 ms 164508 KB Output is correct
6 Correct 555 ms 161212 KB Output is correct
7 Correct 606 ms 160984 KB Output is correct
8 Correct 411 ms 160668 KB Output is correct
9 Correct 606 ms 161092 KB Output is correct
10 Correct 593 ms 160844 KB Output is correct
11 Correct 60 ms 156820 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 58 ms 156848 KB Output is correct
2 Correct 59 ms 156820 KB Output is correct
3 Correct 61 ms 156792 KB Output is correct
4 Correct 57 ms 156844 KB Output is correct
5 Correct 58 ms 156808 KB Output is correct
6 Correct 65 ms 156884 KB Output is correct
7 Correct 58 ms 156736 KB Output is correct
8 Correct 58 ms 156748 KB Output is correct
9 Correct 60 ms 156876 KB Output is correct
10 Correct 61 ms 156864 KB Output is correct
11 Correct 60 ms 156836 KB Output is correct
12 Correct 787 ms 164476 KB Output is correct
13 Correct 1258 ms 159508 KB Output is correct
14 Correct 315 ms 157980 KB Output is correct
15 Correct 1399 ms 160272 KB Output is correct
16 Correct 342 ms 162404 KB Output is correct
17 Correct 682 ms 161148 KB Output is correct
18 Correct 1098 ms 162672 KB Output is correct
19 Correct 975 ms 162896 KB Output is correct
20 Correct 883 ms 162364 KB Output is correct
21 Correct 58 ms 156836 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 60 ms 156812 KB Output is correct
2 Correct 60 ms 156820 KB Output is correct
3 Correct 58 ms 156812 KB Output is correct
4 Correct 63 ms 156784 KB Output is correct
5 Correct 59 ms 156724 KB Output is correct
6 Correct 60 ms 156800 KB Output is correct
7 Correct 63 ms 156876 KB Output is correct
8 Correct 58 ms 156752 KB Output is correct
9 Correct 66 ms 156872 KB Output is correct
10 Correct 59 ms 156748 KB Output is correct
11 Correct 61 ms 156876 KB Output is correct
12 Correct 525 ms 163940 KB Output is correct
13 Correct 458 ms 164464 KB Output is correct
14 Correct 553 ms 161188 KB Output is correct
15 Correct 631 ms 160992 KB Output is correct
16 Correct 414 ms 160548 KB Output is correct
17 Correct 608 ms 161020 KB Output is correct
18 Correct 564 ms 160648 KB Output is correct
19 Correct 780 ms 164380 KB Output is correct
20 Correct 1243 ms 159528 KB Output is correct
21 Correct 321 ms 157904 KB Output is correct
22 Correct 1422 ms 160084 KB Output is correct
23 Correct 356 ms 162588 KB Output is correct
24 Correct 733 ms 161104 KB Output is correct
25 Correct 1110 ms 162876 KB Output is correct
26 Correct 959 ms 162876 KB Output is correct
27 Correct 867 ms 162244 KB Output is correct
28 Correct 660 ms 222488 KB Output is correct
29 Correct 1528 ms 238672 KB Output is correct
30 Correct 3674 ms 214228 KB Output is correct
31 Correct 3487 ms 202252 KB Output is correct
32 Correct 684 ms 165756 KB Output is correct
33 Correct 796 ms 166348 KB Output is correct
34 Correct 890 ms 231972 KB Output is correct
35 Correct 1222 ms 201344 KB Output is correct
36 Correct 2139 ms 236244 KB Output is correct
37 Correct 1831 ms 236276 KB Output is correct
38 Correct 1720 ms 235928 KB Output is correct
39 Correct 1423 ms 220024 KB Output is correct
40 Correct 71 ms 156820 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 68 ms 156748 KB Output is correct
2 Correct 61 ms 156760 KB Output is correct
3 Correct 63 ms 156812 KB Output is correct
4 Correct 61 ms 156796 KB Output is correct
5 Correct 62 ms 156808 KB Output is correct
6 Correct 61 ms 156796 KB Output is correct
7 Correct 63 ms 156816 KB Output is correct
8 Correct 61 ms 156724 KB Output is correct
9 Correct 61 ms 156752 KB Output is correct
10 Correct 64 ms 156848 KB Output is correct
11 Correct 61 ms 156852 KB Output is correct
12 Correct 503 ms 163532 KB Output is correct
13 Correct 459 ms 163824 KB Output is correct
14 Correct 544 ms 160628 KB Output is correct
15 Correct 591 ms 160308 KB Output is correct
16 Correct 401 ms 160052 KB Output is correct
17 Correct 596 ms 160584 KB Output is correct
18 Correct 568 ms 160008 KB Output is correct
19 Correct 806 ms 163844 KB Output is correct
20 Correct 1234 ms 158796 KB Output is correct
21 Correct 316 ms 157424 KB Output is correct
22 Correct 1455 ms 159560 KB Output is correct
23 Correct 355 ms 161868 KB Output is correct
24 Correct 761 ms 160596 KB Output is correct
25 Correct 1113 ms 162408 KB Output is correct
26 Correct 915 ms 162300 KB Output is correct
27 Correct 862 ms 161736 KB Output is correct
28 Correct 669 ms 222160 KB Output is correct
29 Correct 1529 ms 238512 KB Output is correct
30 Correct 3511 ms 214120 KB Output is correct
31 Correct 3302 ms 202216 KB Output is correct
32 Correct 588 ms 165708 KB Output is correct
33 Correct 710 ms 166284 KB Output is correct
34 Correct 753 ms 232292 KB Output is correct
35 Correct 1105 ms 201596 KB Output is correct
36 Correct 2057 ms 236484 KB Output is correct
37 Correct 1722 ms 236696 KB Output is correct
38 Correct 1729 ms 236324 KB Output is correct
39 Runtime error 664 ms 256000 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -