oj.uz

Submission #1080811

# Submission time Handle Problem Language Result Execution time Memory
1080811 2024-08-29T14:30:40 Z Gray Game (IOI13_game) C++17
63 / 100
 921 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, vector<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;
            }
        }
    };
    vector<Node*> leaves;
    Node * root;
    ll rsz;
    SegTree1D(ll N){
        rsz=N;
        root=new Node();
        leaves.resize(N, nullptr);
    }
    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[ind]==nullptr) return 0;
        else 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 0 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 436 KB Output is correct
5 Correct 1 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 348 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 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 1 ms 348 KB Output is correct
2 Correct 1 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 380 ms 32088 KB Output is correct
5 Correct 253 ms 31824 KB Output is correct
6 Correct 327 ms 29512 KB Output is correct
7 Correct 323 ms 29112 KB Output is correct
8 Correct 234 ms 26164 KB Output is correct
9 Correct 318 ms 29268 KB Output is correct
10 Correct 291 ms 29020 KB Output is correct
11 Correct 1 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 1 ms 604 KB Output is correct
3 Correct 1 ms 696 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 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 553 ms 35680 KB Output is correct
13 Correct 724 ms 25680 KB Output is correct
14 Correct 161 ms 8020 KB Output is correct
15 Correct 892 ms 71256 KB Output is correct
16 Correct 143 ms 85080 KB Output is correct
17 Correct 602 ms 76564 KB Output is correct
18 Correct 920 ms 86428 KB Output is correct
19 Correct 791 ms 86612 KB Output is correct
20 Correct 792 ms 86136 KB Output is correct
21 Correct 0 ms 348 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 604 KB Output is correct
6 Correct 1 ms 684 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 604 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 322 ms 31956 KB Output is correct
13 Correct 228 ms 31824 KB Output is correct
14 Correct 293 ms 29524 KB Output is correct
15 Correct 326 ms 29256 KB Output is correct
16 Correct 225 ms 25940 KB Output is correct
17 Correct 314 ms 29264 KB Output is correct
18 Correct 284 ms 29008 KB Output is correct
19 Correct 516 ms 35816 KB Output is correct
20 Correct 746 ms 25684 KB Output is correct
21 Correct 165 ms 8020 KB Output is correct
22 Correct 857 ms 71252 KB Output is correct
23 Correct 151 ms 85072 KB Output is correct
24 Correct 611 ms 76628 KB Output is correct
25 Correct 921 ms 86372 KB Output is correct
26 Correct 811 ms 86736 KB Output is correct
27 Correct 751 ms 86028 KB Output is correct
28 Runtime error 101 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 0 ms 344 KB Output is correct
2 Correct 1 ms 696 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 0 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 0 ms 604 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 322 ms 31860 KB Output is correct
13 Correct 220 ms 31872 KB Output is correct
14 Correct 280 ms 29556 KB Output is correct
15 Correct 322 ms 29096 KB Output is correct
16 Correct 220 ms 25936 KB Output is correct
17 Correct 319 ms 29268 KB Output is correct
18 Correct 267 ms 29008 KB Output is correct
19 Correct 510 ms 35824 KB Output is correct
20 Correct 752 ms 25684 KB Output is correct
21 Correct 166 ms 8020 KB Output is correct
22 Correct 850 ms 71252 KB Output is correct
23 Correct 153 ms 85092 KB Output is correct
24 Correct 610 ms 76740 KB Output is correct
25 Correct 894 ms 86444 KB Output is correct
26 Correct 783 ms 86708 KB Output is correct
27 Correct 753 ms 85980 KB Output is correct
28 Runtime error 86 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -