oj.uz

Submission #477751

# Submission time Handle Problem Language Result Execution time Memory
477751 2021-10-03T11:30:09 Z andrey27_sm Game (IOI13_game) C++17
63 / 100
 1523 ms 256004 KB 
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

ll c, rl;
struct Node{
    Node* lS;
    Node* rS;
    ll val;
    Node(){
        val = 0;
        lS = nullptr;
        rS = nullptr;
    }
};
ll gcd(ll x,ll y){
    if(x == 0 or y == 0) return max(x,y);
    return __gcd(x,y);
}
ll get_val(Node *v){
    if(v == nullptr) return 0;
    return v->val;
}
struct NodeST{
    Node root;
    void update(Node* v,ll l,ll r,ll t,ll val){
        if (l == r){
            (v->val) = val;
            return;
        }
        ll m = (l+r)/2;
        if (t <= m){
            if (v->lS == nullptr) v->lS = new Node();
            update(v->lS,l,m,t,val);
        }else{
            if (v->rS == nullptr) v->rS = new Node();
            update(v->rS,m+1,r,t,val);
        }
        v->val = gcd(get_val(v->lS),get_val(v->rS));
    }
    ll get(Node *v,ll l,ll r,ll tl,ll tr){
        if(v == nullptr or r < tl or tr < l) return 0;
        if(tl <= l and r <= tr) {
            return v->val;
        }
        ll m = (l+r)/2;
        return gcd(get(v->rS,m+1,r,tl,tr),get(v->lS,l,m,tl,tr));
    }
    void update(ll t,ll val){
        return update(&root,0,c,t,val);
    }
    ll get(ll tl,ll tr){
        return get(&root,0,c,tl,tr);
    }
    NodeST(){
        root = *new Node();
    }
};
struct Node2{
    Node2 *lS;
    Node2 *rS;
    NodeST val;
    Node2(){
        lS = nullptr;
        rS = nullptr;
        val = *new NodeST();
    }
};
void update(Node2* v,ll l,ll r,ll x,ll y,ll val){
    if (l == r){
        (v->val).update(y,val);
        return;
    }
    ll m = (l+r)/2;
    if (x <= m){
        if (v->lS == nullptr) v->lS = new Node2();
        update(v->lS,l,m,x,y,val);
    }else{
        if (v->rS == nullptr) v->rS = new Node2();
        update(v->rS,m+1,r,x,y,val);
    }
    ll new_val = 0;
    if(v->lS) new_val=gcd(new_val,(v->lS)->val.get(y,y));
    if(v->rS) new_val=gcd(new_val,(v->rS)->val.get(y,y));
    v->val.update(y,new_val);
}
ll get(Node2 *v,ll l,ll r,ll xl,ll xr,ll yl,ll yr){
    if(v == nullptr or r < xl or xr < l) return 0;
    if(xl <= l and r <= xr) {
        return (v->val).get(yl,yr);
    }
    ll m = (l+r)/2;
    return gcd(get(v->lS,l,m,xl,xr,yl,yr),get(v->rS,m+1,r,xl,xr,yl,yr));
}
Node2 root;
void updates(ll x,ll y,ll val){
    update(&root,0,rl,x,y,val);
}
ll get(ll xl,ll xr,ll yl,ll yr){
    return get(&root,0,rl,xl,xr,yl,yr);
}



/*
int main() {
    int R,C,n;
    cin >> R >> C >> n;
    rl = R+1;
    c = C+1;
    for (int i = 0; i < n; ++i) {
        int type  = 0;
        cin >> type;
        if(type == 1){
            int x,y,t;
            cin >> x >> y >> t;
            updates(x,y,t);
        }
        else{
            int x1,x2,y1,y2;
            cin >> x1 >> y1 >> x2 >> y2;
            cout << get(x1,x2,y1,y2) << "\n";
        }
    }
    return 0;
}
*/
void init(int R,int C){
    rl = R+1;
    c = C+1;
    root = *new Node2();
}
void update(int P,int Q,ll K){
    updates(P,Q,K);
}
ll calculate(int P,int Q,int U,int V){
    return get(P,U,Q,V);
}

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 332 KB Output is correct
3 Correct 1 ms 404 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 0 ms 208 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 1 ms 208 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 208 KB Output is correct
4 Correct 500 ms 17520 KB Output is correct
5 Correct 370 ms 17328 KB Output is correct
6 Correct 501 ms 15060 KB Output is correct
7 Correct 588 ms 14844 KB Output is correct
8 Correct 430 ms 11252 KB Output is correct
9 Correct 555 ms 15012 KB Output is correct
10 Correct 548 ms 14592 KB Output is correct
11 Correct 1 ms 208 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 332 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 288 KB Output is correct
6 Correct 2 ms 336 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 336 KB Output is correct
12 Correct 889 ms 20068 KB Output is correct
13 Correct 1322 ms 10364 KB Output is correct
14 Correct 281 ms 5576 KB Output is correct
15 Correct 1502 ms 13456 KB Output is correct
16 Correct 562 ms 22752 KB Output is correct
17 Correct 767 ms 16764 KB Output is correct
18 Correct 1396 ms 24168 KB Output is correct
19 Correct 1114 ms 24248 KB Output is correct
20 Correct 1069 ms 23708 KB Output is correct
21 Correct 1 ms 208 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 480 ms 17352 KB Output is correct
13 Correct 372 ms 17232 KB Output is correct
14 Correct 503 ms 15160 KB Output is correct
15 Correct 580 ms 14728 KB Output is correct
16 Correct 370 ms 11260 KB Output is correct
17 Correct 531 ms 15136 KB Output is correct
18 Correct 524 ms 14540 KB Output is correct
19 Correct 856 ms 20072 KB Output is correct
20 Correct 1293 ms 10228 KB Output is correct
21 Correct 300 ms 5664 KB Output is correct
22 Correct 1523 ms 13512 KB Output is correct
23 Correct 533 ms 22800 KB Output is correct
24 Correct 802 ms 16652 KB Output is correct
25 Correct 1367 ms 24172 KB Output is correct
26 Correct 1190 ms 24432 KB Output is correct
27 Correct 1134 ms 23684 KB Output is correct
28 Runtime error 968 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 424 KB Output is correct
3 Correct 1 ms 336 KB Output is correct
4 Correct 1 ms 208 KB Output is correct
5 Correct 1 ms 208 KB Output is correct
6 Correct 1 ms 336 KB Output is correct
7 Correct 1 ms 208 KB Output is correct
8 Correct 1 ms 208 KB Output is correct
9 Correct 1 ms 336 KB Output is correct
10 Correct 1 ms 336 KB Output is correct
11 Correct 1 ms 208 KB Output is correct
12 Correct 532 ms 17452 KB Output is correct
13 Correct 386 ms 17296 KB Output is correct
14 Correct 504 ms 15164 KB Output is correct
15 Correct 549 ms 14812 KB Output is correct
16 Correct 385 ms 11236 KB Output is correct
17 Correct 523 ms 14984 KB Output is correct
18 Correct 489 ms 14588 KB Output is correct
19 Correct 810 ms 20120 KB Output is correct
20 Correct 1294 ms 10376 KB Output is correct
21 Correct 279 ms 5656 KB Output is correct
22 Correct 1513 ms 13644 KB Output is correct
23 Correct 551 ms 22728 KB Output is correct
24 Correct 748 ms 16884 KB Output is correct
25 Correct 1291 ms 24224 KB Output is correct
26 Correct 1121 ms 24312 KB Output is correct
27 Correct 1032 ms 23876 KB Output is correct
28 Runtime error 903 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -