oj.uz

Submission #580784

# Submission time Handle Problem Language Result Execution time Memory
580784 2022-06-21T19:41:07 Z Dakto Game (IOI13_game) C++17
63 / 100
 1745 ms 256000 KB 
#include "game.h"

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

struct SegTree{
    struct Node{
        int lb, rb, mid;
        Node* l=0, *r=0;
        long long val=0;
        Node(int lb, int rb):lb(lb), rb(rb){mid=(lb+rb)/2;}
        Node* get(int ind){
            if(ind<=mid) return left();
            else return right();
        }
        Node* left(){
            if(l==0) l=new Node(lb, mid);
            return l;
        }
        Node* right(){
            if(r==0) r=new Node(mid+1, rb);
            return r;
        }
        void set(int ind, long long v){
            if(lb==ind && rb==ind){
                val=v;
                return;
            }
            get(ind)->set(ind, v);
            if(l==0) val = r->val;
            else if(r==0) val = l->val;
            else val=gcd2(l->val, r->val);
        }
        long long query(int lft, int rgh){
            if(lft<=lb && rgh>=rb) return val;
            if(lb>rgh || rb<lft) return 0;
            if(l==0 && r==0) return 0;
            if(l==0) return r->query(lft, rgh);
            if(r==0) return l->query(lft, rgh);
            return gcd2(l->query(lft, rgh), r->query(lft, rgh));
        }
    };
    Node *root;
    SegTree(int n){root=new Node(0, n);}
    void set(int ind, long long val){root->set(ind, val);}
    long long query(int lb, int rb){return root->query(lb, rb);}
    long long vl(int ind){return query(ind, ind);}
};

struct TDS{
    struct Node{
        int lb, rb, mid;
        Node* l=0, *r=0;
        SegTree val;
        int n;
        Node(int lb, int rb, int n):lb(lb), rb(rb), val(n), n(n) {mid=(lb+rb)/2;}
        Node* get(int ind){
            if(ind<=mid) return left();
            else return right();
        }
        Node* left(){
            if(l==0) l=new Node(lb, mid, n);
            return l;
        }
        Node* right(){
            if(r==0) r=new Node(mid+1, rb, n);
            return r;
        }
        void set(int x, int y, long long v){
            if(lb==x && rb==x){
                val.set(y, v);
                return;
            }
            get(x)->set(x, y, v);
            if(l==0) val.set(y,r->val.vl(y));
            else if(r==0) val.set(y, l->val.vl(y));
            else val.set(y, gcd2(l->val.vl(y), r->val.vl(y)));
        }
        long long query(int lft, int rgh, int ylft, int yrgh){
            if(lft<=lb && rgh>=rb) return val.query(ylft, yrgh);
            if(lb>rgh || rb<lft) return 0;
            if(l==0 && r==0) return 0;
            if(l==0) return r->query(lft, rgh, ylft, yrgh);
            if(r==0) return l->query(lft, rgh, ylft, yrgh);
            return gcd2(l->query(lft, rgh, ylft, yrgh), r->query(lft, rgh, ylft, yrgh));
        }
    };
    Node *root;
    TDS(int x, int y){root=new Node(0, x, y+1);};
    void set(int ind, int y, long long val){root->set(ind, y, val);}
    long long query(int lb, int rb, int xl, int xr){return root->query(lb, rb, xl, xr);}
};

TDS* tree;

void init(int R, int C) {
    tree=new TDS(R,C);
}

void update(int P, int Q, long long K) {
    tree->set(P, Q, K);
}

long long calculate(int P, int Q, int U, int V) {
    return tree->query(P,U,Q,V);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 408 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 2 ms 368 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 228 KB Output is correct
12 Correct 0 ms 212 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 546 ms 17308 KB Output is correct
5 Correct 361 ms 17608 KB Output is correct
6 Correct 524 ms 14596 KB Output is correct
7 Correct 588 ms 14388 KB Output is correct
8 Correct 426 ms 9420 KB Output is correct
9 Correct 663 ms 14456 KB Output is correct
10 Correct 526 ms 14156 KB Output is correct
11 Correct 0 ms 212 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 372 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 862 ms 21544 KB Output is correct
13 Correct 1317 ms 8816 KB Output is correct
14 Correct 260 ms 912 KB Output is correct
15 Correct 1647 ms 12768 KB Output is correct
16 Correct 438 ms 26988 KB Output is correct
17 Correct 866 ms 16468 KB Output is correct
18 Correct 1569 ms 27096 KB Output is correct
19 Correct 1368 ms 27492 KB Output is correct
20 Correct 1422 ms 26836 KB Output is correct
21 Correct 0 ms 212 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 529 ms 17284 KB Output is correct
13 Correct 322 ms 17576 KB Output is correct
14 Correct 517 ms 14532 KB Output is correct
15 Correct 549 ms 14388 KB Output is correct
16 Correct 363 ms 9340 KB Output is correct
17 Correct 550 ms 14484 KB Output is correct
18 Correct 586 ms 14156 KB Output is correct
19 Correct 878 ms 21652 KB Output is correct
20 Correct 1432 ms 8880 KB Output is correct
21 Correct 260 ms 984 KB Output is correct
22 Correct 1660 ms 12640 KB Output is correct
23 Correct 461 ms 26904 KB Output is correct
24 Correct 865 ms 16476 KB Output is correct
25 Correct 1745 ms 27128 KB Output is correct
26 Correct 1370 ms 27512 KB Output is correct
27 Correct 1290 ms 26692 KB Output is correct
28 Runtime error 635 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 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 212 KB Output is correct
8 Correct 1 ms 212 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 212 KB Output is correct
12 Correct 572 ms 17356 KB Output is correct
13 Correct 378 ms 17612 KB Output is correct
14 Correct 559 ms 14528 KB Output is correct
15 Correct 624 ms 14292 KB Output is correct
16 Correct 364 ms 9420 KB Output is correct
17 Correct 579 ms 14564 KB Output is correct
18 Correct 585 ms 14152 KB Output is correct
19 Correct 1006 ms 21532 KB Output is correct
20 Correct 1383 ms 8820 KB Output is correct
21 Correct 274 ms 1004 KB Output is correct
22 Correct 1563 ms 12784 KB Output is correct
23 Correct 443 ms 26812 KB Output is correct
24 Correct 854 ms 16488 KB Output is correct
25 Correct 1706 ms 27248 KB Output is correct
26 Correct 1303 ms 27404 KB Output is correct
27 Correct 1298 ms 26740 KB Output is correct
28 Runtime error 553 ms 256000 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -