oj.uz

Submission #477787

# Submission time Handle Problem Language Result Execution time Memory
477787 2021-10-03T17:21:18 Z andrey27_sm Game (IOI13_game) C++17
63 / 100
 1556 ms 256004 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int c, rl;
int y,y1n,y2;
ll vals;
int x;
ll gcd(ll x,ll y){
    if(x == 0 or y == 0) return max(x,y);
    return __gcd(x,y);
}
struct Node{
    Node* lS;
    Node* rS;
    int l, r, m;
    ll val;
    ll tmp_val;
    Node(){
        val = 0;
        lS = nullptr;
        rS = nullptr;
        l = 0;
        r = 0;
        m = 0;
    }
    Node(int l1,int r1){
        val = 0;
        lS = nullptr;
        rS = nullptr;
        l = l1;
        r = r1;
        m = (l+r)/2;
    }
    ll get(int tl,int tr){
        if(tl <= l and r <= tr) return val;
        if(tr <= m){
            if(lS) return lS->get(tl,tr);
            return 0;
        }
        else if(tl > m){
            if(rS) return rS->get(tl,tr);
            return 0;
        }else{
            tmp_val = 0;
            if(lS) tmp_val = lS->get(tl,m);
            if(rS) tmp_val = gcd(tmp_val,(rS->get(m,tr)));
            return tmp_val;
        }
    }
    void update(int y,ll vals){
        if(l == r) {
            val = vals;
            return;
        }
        if(y <= m){
            if(!lS) lS = new Node(l,m);
            lS->update(y,vals);
        }
        if(y > m){
            if(!rS) rS = new Node(m+1,r);
            rS->update(y,vals);
        }
        val = 0;
        if(lS) val = lS->val;
        if(rS) val = gcd(val,rS->val);
    }
};
struct Node2{
    Node2 *lS;
    Node2 *rS;
    Node *root;
    int l,r,m;
    ll tmp_val;
    Node2(){
        lS = nullptr;
        rS = nullptr;
        l = r = 0;
        root = new Node(0,c);
    }
    Node2(int l1,int r1){
        lS = nullptr;
        rS = nullptr;
        l = l1;
        r = r1;
        m = (l+r)/2;
        root = new Node(0,c);
    }
    ll get(int x1,int x2){
        if(x1 <= l and r <= x2) return root->get(y1n,y2);
        if(x2 <= m){
            if(lS) return lS->get(x1,x2);
            return 0;
        }
        else if(x1 > m){
            if(rS) return rS->get(x1,x2);
            return 0;
        }else{
            tmp_val = 0;
            if(lS) tmp_val = lS->get(x1,m);
            if(rS) tmp_val = gcd(tmp_val,(rS->get(m+1,x2)));
            return tmp_val;
        }
    }
    void update(){
        if(l == r){
            root->update(y,vals);
            return;
        }
        if(x <= m){
            if(!lS) lS = new Node2(l,m);
            lS->update();
        }
        if(x > m){
            if(!rS) rS = new Node2(m+1,r);
            rS->update();
        }
        tmp_val = 0;
        if(lS) tmp_val = lS->root->get(y,y);
        if(rS) tmp_val = gcd(tmp_val,rS->root->get(y,y));
        root->update(y,tmp_val);
    }
};

Node2 *root = nullptr;
void init(int R,int C){
    rl = R-1;
    c = C-1;
    root = new Node2(0,rl);
}
void update(int P,int Q,ll K){
    y = Q;
    vals = K;
    x = P;
    root->update();
}
ll calculate(int P,int Q,int U,int V){
    y1n = Q;
    y2 = V;
    return root->get(P,U);
}
/*
int main(){
    int t1,t2,t3;
    cin >> t1 >> t2 >> t3;
    init(t1,t2);
    while (t3--){
        int type;
        cin >> type;
        if(type == 1){
            int x,y;
            ll val;
            cin >> x >> y >> val;
            update(x,y,val);
        }
        if(type == 2){
            int x1,y1,x2,y2;
            cin >> x1 >> y1 >> x2 >> y2;
            cout << calculate(x1,y1,x2,y2) << "\n";
        }
    }
    return 0;
}*/

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 1 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 472 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 0 ms 204 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 0 ms 204 KB Output is correct
3 Correct 1 ms 204 KB Output is correct
4 Correct 536 ms 20844 KB Output is correct
5 Correct 378 ms 21228 KB Output is correct
6 Correct 512 ms 18268 KB Output is correct
7 Correct 556 ms 18024 KB Output is correct
8 Correct 358 ms 11408 KB Output is correct
9 Correct 541 ms 18252 KB Output is correct
10 Correct 522 ms 17744 KB Output is correct
11 Correct 0 ms 204 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 1 ms 204 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 844 ms 27212 KB Output is correct
13 Correct 1268 ms 11208 KB Output is correct
14 Correct 301 ms 964 KB Output is correct
15 Correct 1553 ms 16272 KB Output is correct
16 Correct 270 ms 35432 KB Output is correct
17 Correct 841 ms 21316 KB Output is correct
18 Correct 1494 ms 35804 KB Output is correct
19 Correct 1255 ms 35952 KB Output is correct
20 Correct 1229 ms 35428 KB Output is correct
21 Correct 1 ms 204 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 460 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 565 ms 20896 KB Output is correct
13 Correct 384 ms 21252 KB Output is correct
14 Correct 480 ms 18244 KB Output is correct
15 Correct 564 ms 18028 KB Output is correct
16 Correct 341 ms 11416 KB Output is correct
17 Correct 541 ms 18116 KB Output is correct
18 Correct 496 ms 17764 KB Output is correct
19 Correct 915 ms 27284 KB Output is correct
20 Correct 1335 ms 11204 KB Output is correct
21 Correct 263 ms 964 KB Output is correct
22 Correct 1556 ms 16400 KB Output is correct
23 Correct 251 ms 35372 KB Output is correct
24 Correct 823 ms 21284 KB Output is correct
25 Correct 1488 ms 35884 KB Output is correct
26 Correct 1248 ms 36048 KB Output is correct
27 Correct 1172 ms 35312 KB Output is correct
28 Runtime error 419 ms 256004 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 204 KB Output is correct
2 Correct 1 ms 472 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 1 ms 204 KB Output is correct
5 Correct 1 ms 204 KB Output is correct
6 Correct 1 ms 460 KB Output is correct
7 Correct 0 ms 204 KB Output is correct
8 Correct 0 ms 204 KB Output is correct
9 Correct 1 ms 460 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 521 ms 20936 KB Output is correct
13 Correct 391 ms 21188 KB Output is correct
14 Correct 489 ms 18452 KB Output is correct
15 Correct 545 ms 18116 KB Output is correct
16 Correct 336 ms 11316 KB Output is correct
17 Correct 536 ms 18228 KB Output is correct
18 Correct 492 ms 17680 KB Output is correct
19 Correct 842 ms 27216 KB Output is correct
20 Correct 1215 ms 11204 KB Output is correct
21 Correct 257 ms 1072 KB Output is correct
22 Correct 1522 ms 16300 KB Output is correct
23 Correct 251 ms 35396 KB Output is correct
24 Correct 819 ms 21340 KB Output is correct
25 Correct 1496 ms 36028 KB Output is correct
26 Correct 1249 ms 35896 KB Output is correct
27 Correct 1180 ms 35408 KB Output is correct
28 Runtime error 432 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -