oj.uz

Submission #590414

# Submission time Handle Problem Language Result Execution time Memory
590414 2022-07-05T22:48:51 Z jeroenodb Game (IOI13_game) C++17
100 / 100
 8183 ms 73324 KB 
#include "game.h"
#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
ll r,c;
ll ans=0;
struct node2 {
    ll pos=-1,len;
    ll g=0,lazy=0;
    node2 *l=NULL, *r = NULL;
    node2(ll n) : len(n) {}
    static ll total(node2* nd) {
        return nd?gcd(nd->g,nd->lazy):0LL;
    }
    void query(ll a, ll b) const {
        if(b<0 or a>=len) return;
        if(pos!=-1 and a<=pos and pos<=b) ans = gcd(ans,lazy);
        if(a<=0 and b>=len-1) {
            ans = gcd(ans,g);
            return;
        }
        ll mid = len/2;
        if(l) l->query(a,b);
        if(r) r->query(a-mid,b-mid);
    }
    void update(ll y, ll v) {
        if(y==pos or pos==-1) {
            pos = y;
            lazy=v;
            return;
        }
        ll mid = len/2;
        if(y<mid) {
            if(!l) l = new node2(mid);
            l->update(y,v);
        } else {
            if(!r) r = new node2(len-mid);
            r->update(y-mid,v);
        }
        g = gcd(total(l),total(r));
    }
};
struct node {
    node *l = NULL, *r = NULL;
    int len; // make it power of 2?
    node2 *sub = NULL;
    node(int n) : len(n) {}
    node() {}
    void query(int cc, int dd, int a,int b) const {
        if(dd<0 or cc>=len) return;
        int mid = len/2;
        if(cc<=0 and dd>=len-1) {
            if(sub) sub->query(a*::r,b*::r+::r-1);
            return;
        }
        if(l) l->query(cc,dd,a,b);
        if(r) r->query(cc-mid,dd-mid,a,b);
    }
    void update(int x, int y, ll v) {
        
        if(!sub) sub = new node2(c*::r);
        sub->update(y*::r + x,v);
        if(len==1) return;
        int mid = len/2;
        if(x<mid) {
            if(!l) l = new node(mid);
            l->update(x,y,v);
        } else {
            if(!r) r = new node(len-mid);
            r->update(x-mid,y,v);
        }
    }
} root;

vvi a;
void init(int R, int C) {
    r=R,c=C;
    // a.assign(R,vi(C));
    root = node(R);
}

vi queries;
void update(int P, int Q, long long K) {
    // cout << "1 " << P << ' ' << Q << ' ' << K << '\n';
    // a[P][Q]=K;
    root.update(P,Q,K);
}

long long calculate(int P, int Q, int U, int V) {
    
    ans=0;
    root.query(P,U,Q,V);
    // cout << "2 " << P << ' ' << Q << ' ' << U << ' ' << V << '\n';
    // ll bans=0;
    // for(int i=P;i<=U;++i) {
    //     for(int j=Q;j<=V;++j) {
    //         bans=gcd(bans,a[i][j]);
    //     }
    // }
    // if(ans!=bans) {
    //     exit(0);
    // }
    return ans;
}
std::mt19937 rng(std::chrono::steady_clock::now().time_since_epoch().count());
template<class I> I rnd(I l,I r){return std::uniform_int_distribution<I>(l,r)(rng);}
#ifdef LOCALfg
int main() {
    while(true) {
        int R = rnd(2,4),C = rnd(2,4);
        cout << "TEST!\n";
        cout << R << ' '<< C << '\n';
        init(R,C);
        for(int i=0;i<6;++i) {
            if(rnd(0,1)==0) {
                update(rnd(0,R-1),rnd(0,C-1), rnd(0,50));
            } else {
                auto get = [&](int B) {
                    int l=rnd(0,B-1),r=rnd(0,B-1);
                    if(l>r) swap(l,r);
                    return pi{l,r};
                };
                auto [P,U] = get(R);
                auto [Q,V] = get(C);
                calculate(P,Q,U,V);
            }
        }
    }
}
#endif

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 304 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 340 KB Output is correct
11 Correct 1 ms 308 KB Output is correct
12 Correct 0 ms 212 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 308 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 554 ms 7180 KB Output is correct
5 Correct 407 ms 7392 KB Output is correct
6 Correct 446 ms 8728 KB Output is correct
7 Correct 493 ms 8472 KB Output is correct
8 Correct 324 ms 7368 KB Output is correct
9 Correct 472 ms 8552 KB Output is correct
10 Correct 472 ms 8168 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 1 ms 212 KB Output is correct
2 Correct 1 ms 300 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 212 KB Output is correct
12 Correct 1101 ms 15336 KB Output is correct
13 Correct 2479 ms 9932 KB Output is correct
14 Correct 325 ms 5664 KB Output is correct
15 Correct 2850 ms 11100 KB Output is correct
16 Correct 184 ms 12872 KB Output is correct
17 Correct 673 ms 10112 KB Output is correct
18 Correct 1140 ms 14384 KB Output is correct
19 Correct 982 ms 14332 KB Output is correct
20 Correct 1020 ms 13864 KB Output is correct
21 Correct 0 ms 212 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 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 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 545 ms 11604 KB Output is correct
13 Correct 412 ms 11176 KB Output is correct
14 Correct 441 ms 8648 KB Output is correct
15 Correct 479 ms 8676 KB Output is correct
16 Correct 335 ms 7380 KB Output is correct
17 Correct 516 ms 8588 KB Output is correct
18 Correct 451 ms 8164 KB Output is correct
19 Correct 1093 ms 15480 KB Output is correct
20 Correct 2541 ms 9956 KB Output is correct
21 Correct 317 ms 5660 KB Output is correct
22 Correct 2761 ms 11068 KB Output is correct
23 Correct 176 ms 12876 KB Output is correct
24 Correct 682 ms 10212 KB Output is correct
25 Correct 1147 ms 14448 KB Output is correct
26 Correct 966 ms 14512 KB Output is correct
27 Correct 897 ms 13952 KB Output is correct
28 Correct 483 ms 39024 KB Output is correct
29 Correct 1402 ms 41756 KB Output is correct
30 Correct 5677 ms 31632 KB Output is correct
31 Correct 4508 ms 25952 KB Output is correct
32 Correct 526 ms 10672 KB Output is correct
33 Correct 594 ms 11332 KB Output is correct
34 Correct 269 ms 35528 KB Output is correct
35 Correct 823 ms 25216 KB Output is correct
36 Correct 1567 ms 39580 KB Output is correct
37 Correct 1242 ms 39776 KB Output is correct
38 Correct 1277 ms 39164 KB Output is correct
39 Correct 1088 ms 33064 KB Output is correct
40 Correct 0 ms 212 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 300 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 308 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 304 KB Output is correct
12 Correct 560 ms 11468 KB Output is correct
13 Correct 414 ms 11220 KB Output is correct
14 Correct 480 ms 8644 KB Output is correct
15 Correct 480 ms 8384 KB Output is correct
16 Correct 332 ms 7460 KB Output is correct
17 Correct 518 ms 8472 KB Output is correct
18 Correct 451 ms 8248 KB Output is correct
19 Correct 1085 ms 15348 KB Output is correct
20 Correct 2529 ms 9864 KB Output is correct
21 Correct 352 ms 5700 KB Output is correct
22 Correct 2837 ms 11104 KB Output is correct
23 Correct 203 ms 12876 KB Output is correct
24 Correct 711 ms 10112 KB Output is correct
25 Correct 1142 ms 14304 KB Output is correct
26 Correct 991 ms 14396 KB Output is correct
27 Correct 948 ms 13816 KB Output is correct
28 Correct 538 ms 39012 KB Output is correct
29 Correct 1404 ms 41648 KB Output is correct
30 Correct 5994 ms 31788 KB Output is correct
31 Correct 5194 ms 26068 KB Output is correct
32 Correct 513 ms 10632 KB Output is correct
33 Correct 571 ms 11344 KB Output is correct
34 Correct 257 ms 35384 KB Output is correct
35 Correct 828 ms 25292 KB Output is correct
36 Correct 1575 ms 39496 KB Output is correct
37 Correct 1299 ms 39664 KB Output is correct
38 Correct 1248 ms 39152 KB Output is correct
39 Correct 719 ms 71200 KB Output is correct
40 Correct 2094 ms 73324 KB Output is correct
41 Correct 8183 ms 60280 KB Output is correct
42 Correct 7635 ms 47128 KB Output is correct
43 Correct 365 ms 68000 KB Output is correct
44 Correct 1010 ms 12104 KB Output is correct
45 Correct 1047 ms 33108 KB Output is correct
46 Correct 2232 ms 71972 KB Output is correct
47 Correct 2149 ms 71964 KB Output is correct
48 Correct 2068 ms 71664 KB Output is correct
49 Correct 1 ms 212 KB Output is correct