oj.uz

Submission #477782

# Submission time Handle Problem Language Result Execution time Memory
477782 2021-10-03T17:08:04 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;

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,int y1,int y2){
        if(x1 <= l and r <= x2) return root->get(y1,y2);
        if(x2 <= m){
            if(lS) return lS->get(x1,x2,y1,y2);
            return 0;
        }
        else if(x1 > m){
            if(rS) return rS->get(x1,x2,y1,y2);
            return 0;
        }else{
            tmp_val = 0;
            if(lS) tmp_val = lS->get(x1,m,y1,y2);
            if(rS) tmp_val = gcd(tmp_val,(rS->get(m+1,x2,y1,y2)));
            return tmp_val;
        }
    }
    void update(int x,int y,ll vals){
        if(l == r){
            root->update(y,vals);
            return;
        }
        if(x <= m){
            if(!lS) lS = new Node2(l,m);
            lS->update(x,y,vals);
        }
        if(x > m){
            if(!rS) rS = new Node2(m+1,r);
            rS->update(x,y,vals);
        }
        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){
    root->update(P,Q,K);
}
ll calculate(int P,int Q,int U,int V){
    return root->get(P,U,Q,V);
}
/*
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 1 ms 204 KB Output is correct
5 Correct 0 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 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 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 533 ms 20924 KB Output is correct
5 Correct 394 ms 21220 KB Output is correct
6 Correct 549 ms 18260 KB Output is correct
7 Correct 574 ms 18068 KB Output is correct
8 Correct 390 ms 11332 KB Output is correct
9 Correct 562 ms 18236 KB Output is correct
10 Correct 520 ms 17772 KB Output is correct
11 Correct 1 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 1 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 925 ms 27196 KB Output is correct
13 Correct 1303 ms 11280 KB Output is correct
14 Correct 267 ms 964 KB Output is correct
15 Correct 1548 ms 16556 KB Output is correct
16 Correct 264 ms 35416 KB Output is correct
17 Correct 864 ms 21388 KB Output is correct
18 Correct 1537 ms 35928 KB Output is correct
19 Correct 1310 ms 35980 KB Output is correct
20 Correct 1215 ms 35252 KB Output is correct
21 Correct 0 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 0 ms 204 KB Output is correct
5 Correct 0 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 500 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 332 KB Output is correct
12 Correct 532 ms 20944 KB Output is correct
13 Correct 399 ms 21156 KB Output is correct
14 Correct 502 ms 18224 KB Output is correct
15 Correct 565 ms 18076 KB Output is correct
16 Correct 349 ms 11396 KB Output is correct
17 Correct 538 ms 18116 KB Output is correct
18 Correct 515 ms 17920 KB Output is correct
19 Correct 858 ms 27264 KB Output is correct
20 Correct 1287 ms 11264 KB Output is correct
21 Correct 262 ms 1028 KB Output is correct
22 Correct 1507 ms 16380 KB Output is correct
23 Correct 260 ms 35524 KB Output is correct
24 Correct 841 ms 21316 KB Output is correct
25 Correct 1556 ms 35924 KB Output is correct
26 Correct 1294 ms 35952 KB Output is correct
27 Correct 1204 ms 35268 KB Output is correct
28 Runtime error 450 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 1 ms 276 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 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 538 ms 20896 KB Output is correct
13 Correct 400 ms 21276 KB Output is correct
14 Correct 486 ms 18244 KB Output is correct
15 Correct 549 ms 18040 KB Output is correct
16 Correct 347 ms 11408 KB Output is correct
17 Correct 547 ms 18192 KB Output is correct
18 Correct 511 ms 17916 KB Output is correct
19 Correct 858 ms 27304 KB Output is correct
20 Correct 1284 ms 11260 KB Output is correct
21 Correct 258 ms 1052 KB Output is correct
22 Correct 1508 ms 16552 KB Output is correct
23 Correct 248 ms 35468 KB Output is correct
24 Correct 828 ms 21412 KB Output is correct
25 Correct 1508 ms 35828 KB Output is correct
26 Correct 1279 ms 35860 KB Output is correct
27 Correct 1182 ms 35164 KB Output is correct
28 Runtime error 424 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -