oj.uz

Submission #1080837

# Submission time Handle Problem Language Result Execution time Memory
1080837 2024-08-29T14:45:13 Z Gray Game (IOI13_game) C++17
63 / 100
 2550 ms 256000 KB 
#include<bits/stdc++.h>
#include "game.h"
#define ll long long
#define ff first
#define ss second
#define ln "\n"
using namespace std;
struct SegTree1D{
    struct Node{
        map<ll, Node*> con;
        ll gcd;
        Node(){
            gcd=0;
        }
        void update(ll tl, ll tr, ll i, ll x, map<ll, Node*> &leaves){
            if (tl==tr){
                gcd=x;
                leaves[tl]=this;
            }else{
                ll tm = (tl+tr)/2;
                if (i<=tm) {
                    if (!con.count(0)) con[0]=new Node();
                    con[0]->update(tl, tm, i, x, leaves);
                }else{
                    if (!con.count(1)) con[1]=new Node();
                    con[1]->update(tm+1, tr, i, x, leaves);
                }
                gcd=0;
                if(con.count(0)) gcd=__gcd(con[0]->gcd, gcd);
                if (con.count(1)) gcd=__gcd(con[1]->gcd, gcd);
            }
        }
        ll query(ll tl, ll tr, ll l, ll r){
            if (tl==l and tr==r){
                return gcd;
            }else if (l>r) return 0;
            else{
                ll tm = (tl+tr)/2;
                ll ret=0;
                if (con.count(0) and l<=min(r, tm)) ret=__gcd(ret, con[0]->query(tl, tm, l, min(r, tm)));
                if (con.count(1) and max(l, tm+1)<=r) ret=__gcd(ret, con[1]->query(tm+1, tr, max(l, tm+1), r));
                return ret;
            }
        }
    };
    map<ll, Node*> leaves;
    Node * root;
    ll rsz;
    SegTree1D(ll N){
        rsz=N;
        root=new Node();
    }
    void update(ll i, ll x){
        root->update(0, rsz-1, i, x, leaves);
    }
    ll query(ll l, ll r){
        return root->query(0, rsz-1, l, r);
    }
    ll getval(ll ind){
        if (!leaves.count(ind)) return 0;
        return leaves[ind]->gcd;
    }
};
struct SegTree2D{
    struct mNode{
        map<ll, mNode*> con;
        SegTree1D *val;
        ll csz;
        mNode(ll _csz){
            csz=_csz;
            val = new SegTree1D(csz);
        }
        void update(ll tl, ll tr, ll i, ll j, ll x){
            if (tl==tr){
                val->update(j, x);
            }else{
                ll tm = (tl+tr)/2;
                if (i<=tm){
                    if (!con.count(0)) con[0]=new mNode(csz);
                    con[0]->update(tl, tm, i, j, x);
                }else{
                    if (!con.count(1)) con[1]=new mNode(csz);
                    con[1]->update(tm+1, tr, i, j, x);
                }
                val->update(j, __gcd((con.count(0)?con[0]->val->getval(j):0), (con.count(1)?con[1]->val->getval(j):0)));
            }
        }
        ll query(ll li, ll ri, ll lj, ll rj, ll tl, ll tr){
            if (tl==li and tr==ri){
                return val->query(lj, rj);
            }else if (li>ri) return 0;
            else{
                ll ret=0;
                ll tm = (tl+tr)/2;
                if (con.count(0) and li<=min(ri, tm)) ret=__gcd(ret, con[0]->query(li, min(ri, tm), lj, rj, tl, tm));
                if (con.count(1) and max(li, tm+1)<=ri) ret=__gcd(ret, con[1]->query(max(li, tm+1), ri, lj, rj, tm+1, tr));
                return ret;
            }
        }
    };
    mNode * root;
    ll csz, rsz;
    void init(ll R, ll C){
        rsz=R; csz=C;
        root = new mNode(csz);
    }
    void update(ll i, ll j, ll x){
        root->update(0, rsz-1, i, j, x);
    }
    ll query(ll li, ll ri, ll lj, ll rj){
        return root->query(li, ri, lj, rj, 0, rsz-1);
    }
} DS;


void init(int R, int C) {
    DS.init(R, C);
}

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

long long calculate(int P, int Q, int U, int V) {
    /* ... */
    return DS.query(P, U, Q, V);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 0 ms 344 KB Output is correct
6 Correct 1 ms 940 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 0 ms 348 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 795 ms 44600 KB Output is correct
5 Correct 544 ms 44468 KB Output is correct
6 Correct 695 ms 42580 KB Output is correct
7 Correct 663 ms 42320 KB Output is correct
8 Correct 483 ms 26448 KB Output is correct
9 Correct 701 ms 42748 KB Output is correct
10 Correct 698 ms 42036 KB Output is correct
11 Correct 0 ms 344 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 860 KB Output is correct
3 Correct 2 ms 688 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 432 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 680 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1324 ms 59176 KB Output is correct
13 Correct 1742 ms 28096 KB Output is correct
14 Correct 285 ms 6140 KB Output is correct
15 Correct 2224 ms 39692 KB Output is correct
16 Correct 276 ms 80280 KB Output is correct
17 Correct 1322 ms 49380 KB Output is correct
18 Correct 2550 ms 81604 KB Output is correct
19 Correct 2009 ms 81768 KB Output is correct
20 Correct 1935 ms 81016 KB Output is correct
21 Correct 1 ms 344 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 856 KB Output is correct
3 Correct 2 ms 860 KB Output is correct
4 Correct 1 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 928 KB Output is correct
7 Correct 0 ms 604 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 815 ms 44732 KB Output is correct
13 Correct 494 ms 44584 KB Output is correct
14 Correct 588 ms 42564 KB Output is correct
15 Correct 681 ms 42324 KB Output is correct
16 Correct 416 ms 26452 KB Output is correct
17 Correct 630 ms 42672 KB Output is correct
18 Correct 620 ms 42172 KB Output is correct
19 Correct 1312 ms 59220 KB Output is correct
20 Correct 1657 ms 28244 KB Output is correct
21 Correct 234 ms 6224 KB Output is correct
22 Correct 1907 ms 39656 KB Output is correct
23 Correct 258 ms 80264 KB Output is correct
24 Correct 1145 ms 49232 KB Output is correct
25 Correct 2126 ms 81492 KB Output is correct
26 Correct 1746 ms 81868 KB Output is correct
27 Correct 1808 ms 81236 KB Output is correct
28 Runtime error 255 ms 256000 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 348 KB Output is correct
2 Correct 1 ms 860 KB Output is correct
3 Correct 1 ms 860 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 860 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 860 KB Output is correct
10 Correct 1 ms 604 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 714 ms 44672 KB Output is correct
13 Correct 532 ms 44428 KB Output is correct
14 Correct 596 ms 42576 KB Output is correct
15 Correct 673 ms 42372 KB Output is correct
16 Correct 385 ms 26416 KB Output is correct
17 Correct 633 ms 42576 KB Output is correct
18 Correct 623 ms 42228 KB Output is correct
19 Correct 1247 ms 59092 KB Output is correct
20 Correct 1607 ms 28272 KB Output is correct
21 Correct 239 ms 6368 KB Output is correct
22 Correct 1978 ms 39616 KB Output is correct
23 Correct 256 ms 80308 KB Output is correct
24 Correct 1137 ms 49232 KB Output is correct
25 Correct 2259 ms 81492 KB Output is correct
26 Correct 1869 ms 81852 KB Output is correct
27 Correct 1764 ms 81092 KB Output is correct
28 Runtime error 254 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -