oj.uz

Submission #1080783

# Submission time Handle Problem Language Result Execution time Memory
1080783 2024-08-29T14:14:56 Z Gray Game (IOI13_game) C++17
63 / 100
 1145 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 populate(){
            if (left!=nullptr) return;
            left=new Node();
            right=new Node();
        }
        void update(ll tl, ll tr, ll i, ll x, vector<Node*> &leaves){
            if (tl==tr){
                gcd=x;
                leaves[tl]=this;
            }else{
                populate();
                ll tm = (tl+tr)/2;
                if (i<=tm) {
                    left->update(tl, tm, i, x, leaves);
                }else{
                    right->update(tm+1, tr, i, x, leaves);
                }
                gcd=__gcd(left->gcd, right->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 populate(){
            if (!left){
                left=new mNode(csz);
                right=new mNode(csz);
            }
        }
        void update(ll tl, ll tr, ll i, ll j, ll x){
            if (tl==tr){
                val->update(j, x);
            }else{
                populate();
                ll tm = (tl+tr)/2;
                if (i<=tm){
                    left->update(tl, tm, i, j, x);
                }else{
                    right->update(tm+1, tr, i, j, x);
                }
                val->update(j, __gcd(left->val->getval(j), right->val->getval(j)));
            }
        }
        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 1 ms 348 KB Output is correct
5 Correct 1 ms 604 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 432 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 1 ms 428 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 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 348 KB Output is correct
3 Correct 0 ms 604 KB Output is correct
4 Correct 340 ms 37708 KB Output is correct
5 Correct 218 ms 37456 KB Output is correct
6 Correct 326 ms 35152 KB Output is correct
7 Correct 342 ms 35072 KB Output is correct
8 Correct 249 ms 29276 KB Output is correct
9 Correct 334 ms 35032 KB Output is correct
10 Correct 332 ms 34784 KB Output is correct
11 Correct 0 ms 348 KB Output is correct

Subtask #3
26.0 / 26.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 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 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 604 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 567 ms 42484 KB Output is correct
13 Correct 739 ms 28472 KB Output is correct
14 Correct 174 ms 8892 KB Output is correct
15 Correct 930 ms 79540 KB Output is correct
16 Correct 156 ms 96596 KB Output is correct
17 Correct 653 ms 85844 KB Output is correct
18 Correct 1145 ms 97984 KB Output is correct
19 Correct 924 ms 98340 KB Output is correct
20 Correct 834 ms 97540 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 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 1 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 1 ms 600 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 0 ms 604 KB Output is correct
11 Correct 1 ms 344 KB Output is correct
12 Correct 339 ms 37640 KB Output is correct
13 Correct 229 ms 37460 KB Output is correct
14 Correct 346 ms 35152 KB Output is correct
15 Correct 370 ms 34900 KB Output is correct
16 Correct 241 ms 29264 KB Output is correct
17 Correct 341 ms 35156 KB Output is correct
18 Correct 318 ms 34640 KB Output is correct
19 Correct 540 ms 42320 KB Output is correct
20 Correct 848 ms 28328 KB Output is correct
21 Correct 189 ms 9044 KB Output is correct
22 Correct 909 ms 79440 KB Output is correct
23 Correct 157 ms 96604 KB Output is correct
24 Correct 690 ms 85844 KB Output is correct
25 Correct 1045 ms 98136 KB Output is correct
26 Correct 903 ms 98132 KB Output is correct
27 Correct 852 ms 97460 KB Output is correct
28 Runtime error 132 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 348 KB Output is correct
2 Correct 1 ms 604 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 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 604 KB Output is correct
10 Correct 0 ms 604 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 346 ms 37716 KB Output is correct
13 Correct 237 ms 37588 KB Output is correct
14 Correct 311 ms 35364 KB Output is correct
15 Correct 370 ms 34896 KB Output is correct
16 Correct 246 ms 29268 KB Output is correct
17 Correct 333 ms 35096 KB Output is correct
18 Correct 304 ms 34644 KB Output is correct
19 Correct 524 ms 42484 KB Output is correct
20 Correct 735 ms 28376 KB Output is correct
21 Correct 185 ms 8820 KB Output is correct
22 Correct 911 ms 79356 KB Output is correct
23 Correct 176 ms 96600 KB Output is correct
24 Correct 642 ms 85844 KB Output is correct
25 Correct 1012 ms 97944 KB Output is correct
26 Correct 894 ms 98316 KB Output is correct
27 Correct 845 ms 97584 KB Output is correct
28 Runtime error 112 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -