oj.uz

Submission #1080827

# Submission time Handle Problem Language Result Execution time Memory
1080827 2024-08-29T14:39:14 Z Gray Game (IOI13_game) C++17
63 / 100
 1000 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{
        Node *left, *right;
        ll gcd;
        Node(){
            left=right=nullptr; 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 (!left) left=new Node();
                    left->update(tl, tm, i, x, leaves);
                }else{
                    if (!right) right=new Node();
                    right->update(tm+1, tr, i, x, leaves);
                }
                gcd=0;
                if(left) gcd=__gcd(left->gcd, gcd);
                if (right) gcd=__gcd(right->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 (left and l<=min(r, tm)) ret=__gcd(ret, left->query(tl, tm, l, min(r, tm)));
                if (right and max(l, tm+1)<=r) ret=__gcd(ret, right->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{
        mNode *left, *right;
        SegTree1D *val;
        ll csz;
        mNode(ll _csz){
            csz=_csz;
            left=right=nullptr;
            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 (!left) left=new mNode(csz);
                    left->update(tl, tm, i, j, x);
                }else{
                    if (!right) right=new mNode(csz);
                    right->update(tm+1, tr, i, j, x);
                }
                val->update(j, __gcd((left?left->val->getval(j):0), (right?right->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 (left and li<=min(ri, tm)) ret=__gcd(ret, left->query(li, min(ri, tm), lj, rj, tl, tm));
                if (right and max(li, tm+1)<=ri) ret=__gcd(ret, right->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 1 ms 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 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 604 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 1 ms 344 KB Output is correct
9 Correct 1 ms 344 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 1 ms 348 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 398 ms 15328 KB Output is correct
5 Correct 282 ms 15700 KB Output is correct
6 Correct 371 ms 12624 KB Output is correct
7 Correct 438 ms 12372 KB Output is correct
8 Correct 295 ms 7924 KB Output is correct
9 Correct 350 ms 12372 KB Output is correct
10 Correct 414 ms 11908 KB Output is correct
11 Correct 1 ms 348 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 1 ms 600 KB Output is correct
3 Correct 2 ms 600 KB Output is correct
4 Correct 1 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 604 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 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 621 ms 20752 KB Output is correct
13 Correct 804 ms 9064 KB Output is correct
14 Correct 177 ms 1036 KB Output is correct
15 Correct 951 ms 12596 KB Output is correct
16 Correct 236 ms 24720 KB Output is correct
17 Correct 630 ms 14928 KB Output is correct
18 Correct 984 ms 24880 KB Output is correct
19 Correct 878 ms 25216 KB Output is correct
20 Correct 824 ms 24368 KB Output is correct
21 Correct 1 ms 348 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 344 KB Output is correct
6 Correct 1 ms 604 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 1 ms 348 KB Output is correct
10 Correct 1 ms 504 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 348 ms 15424 KB Output is correct
13 Correct 267 ms 15768 KB Output is correct
14 Correct 332 ms 12560 KB Output is correct
15 Correct 346 ms 12368 KB Output is correct
16 Correct 227 ms 8016 KB Output is correct
17 Correct 368 ms 12368 KB Output is correct
18 Correct 298 ms 12124 KB Output is correct
19 Correct 624 ms 20724 KB Output is correct
20 Correct 769 ms 8872 KB Output is correct
21 Correct 156 ms 1108 KB Output is correct
22 Correct 946 ms 12372 KB Output is correct
23 Correct 180 ms 24568 KB Output is correct
24 Correct 559 ms 14928 KB Output is correct
25 Correct 1000 ms 24992 KB Output is correct
26 Correct 829 ms 25392 KB Output is correct
27 Correct 765 ms 24360 KB Output is correct
28 Runtime error 634 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 344 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 600 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 604 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 344 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 351 ms 15460 KB Output is correct
13 Correct 235 ms 15544 KB Output is correct
14 Correct 349 ms 12628 KB Output is correct
15 Correct 339 ms 12212 KB Output is correct
16 Correct 212 ms 8060 KB Output is correct
17 Correct 338 ms 12316 KB Output is correct
18 Correct 288 ms 12088 KB Output is correct
19 Correct 620 ms 20740 KB Output is correct
20 Correct 753 ms 9044 KB Output is correct
21 Correct 181 ms 1104 KB Output is correct
22 Correct 913 ms 12480 KB Output is correct
23 Correct 176 ms 24660 KB Output is correct
24 Correct 584 ms 14948 KB Output is correct
25 Correct 943 ms 24824 KB Output is correct
26 Correct 826 ms 25184 KB Output is correct
27 Correct 843 ms 24588 KB Output is correct
28 Runtime error 574 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -