oj.uz

Submission #1080823

# Submission time Handle Problem Language Result Execution time Memory
1080823 2024-08-29T14:36:53 Z Gray Game (IOI13_game) C++17
63 / 100
 875 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[ind]==nullptr) 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 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 0 ms 348 KB Output is correct
6 Correct 1 ms 508 KB Output is correct
7 Correct 0 ms 360 KB Output is correct
8 Correct 1 ms 348 KB Output is correct
9 Correct 1 ms 600 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 1 ms 348 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 0 ms 348 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 334 ms 17252 KB Output is correct
5 Correct 217 ms 17748 KB Output is correct
6 Correct 301 ms 14672 KB Output is correct
7 Correct 331 ms 14488 KB Output is correct
8 Correct 217 ms 8868 KB Output is correct
9 Correct 327 ms 14348 KB Output is correct
10 Correct 285 ms 14164 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 348 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 616 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 476 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 557 ms 24260 KB Output is correct
13 Correct 730 ms 10836 KB Output is correct
14 Correct 157 ms 1108 KB Output is correct
15 Correct 860 ms 14928 KB Output is correct
16 Correct 167 ms 29264 KB Output is correct
17 Correct 537 ms 17456 KB Output is correct
18 Correct 847 ms 29524 KB Output is correct
19 Correct 744 ms 29812 KB Output is correct
20 Correct 697 ms 29012 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 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 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 600 KB Output is correct
10 Correct 1 ms 344 KB Output is correct
11 Correct 1 ms 348 KB Output is correct
12 Correct 318 ms 17404 KB Output is correct
13 Correct 215 ms 17744 KB Output is correct
14 Correct 300 ms 14588 KB Output is correct
15 Correct 325 ms 14416 KB Output is correct
16 Correct 223 ms 8924 KB Output is correct
17 Correct 311 ms 14472 KB Output is correct
18 Correct 276 ms 14160 KB Output is correct
19 Correct 514 ms 24400 KB Output is correct
20 Correct 732 ms 10696 KB Output is correct
21 Correct 176 ms 1104 KB Output is correct
22 Correct 840 ms 15080 KB Output is correct
23 Correct 159 ms 29264 KB Output is correct
24 Correct 542 ms 17676 KB Output is correct
25 Correct 845 ms 29520 KB Output is correct
26 Correct 755 ms 29776 KB Output is correct
27 Correct 691 ms 29008 KB Output is correct
28 Runtime error 513 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 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 1 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 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 356 ms 17320 KB Output is correct
13 Correct 217 ms 17744 KB Output is correct
14 Correct 297 ms 14492 KB Output is correct
15 Correct 321 ms 14456 KB Output is correct
16 Correct 213 ms 9044 KB Output is correct
17 Correct 311 ms 14420 KB Output is correct
18 Correct 304 ms 14164 KB Output is correct
19 Correct 532 ms 24272 KB Output is correct
20 Correct 793 ms 10832 KB Output is correct
21 Correct 158 ms 1104 KB Output is correct
22 Correct 841 ms 14864 KB Output is correct
23 Correct 160 ms 29264 KB Output is correct
24 Correct 528 ms 17476 KB Output is correct
25 Correct 875 ms 29524 KB Output is correct
26 Correct 772 ms 29596 KB Output is correct
27 Correct 705 ms 29200 KB Output is correct
28 Runtime error 514 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -