oj.uz

Submission #477767

# Submission time Handle Problem Language Result Execution time Memory
477767 2021-10-03T12:00:59 Z andrey27_sm Game (IOI13_game) C++17
63 / 100
 1587 ms 256004 KB 
#pragma dynamic
#include "game.h"
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

int 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,int l,int r,int 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,int l,int r,int tl,int 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,int l,int r,int x,int 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,int l,int r,int xl,int xr,int yl,int 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(int x,int y,ll val){
    update(&root,0,rl,x,y,val);
}
ll get(int xl,int xr,int yl,int 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);
}

Compilation message

game.cpp:1: warning: ignoring '#pragma dynamic ' [-Wunknown-pragmas]
    1 | #pragma dynamic
      |

Subtask #1
10.0 / 10.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 332 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 2 ms 332 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 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 204 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 1 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 504 ms 13124 KB Output is correct
5 Correct 385 ms 13508 KB Output is correct
6 Correct 485 ms 10448 KB Output is correct
7 Correct 534 ms 10104 KB Output is correct
8 Correct 378 ms 6992 KB Output is correct
9 Correct 524 ms 10308 KB Output is correct
10 Correct 543 ms 9916 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 1 ms 224 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 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 332 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 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 842 ms 15996 KB Output is correct
13 Correct 1324 ms 6312 KB Output is correct
14 Correct 306 ms 992 KB Output is correct
15 Correct 1488 ms 9036 KB Output is correct
16 Correct 536 ms 18628 KB Output is correct
17 Correct 870 ms 11756 KB Output is correct
18 Correct 1389 ms 18880 KB Output is correct
19 Correct 1224 ms 18936 KB Output is correct
20 Correct 1235 ms 18332 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 1 ms 204 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 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 332 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 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 550 ms 13000 KB Output is correct
13 Correct 396 ms 13312 KB Output is correct
14 Correct 517 ms 10420 KB Output is correct
15 Correct 554 ms 10096 KB Output is correct
16 Correct 359 ms 6968 KB Output is correct
17 Correct 517 ms 10280 KB Output is correct
18 Correct 481 ms 9872 KB Output is correct
19 Correct 855 ms 15864 KB Output is correct
20 Correct 1350 ms 6244 KB Output is correct
21 Correct 293 ms 840 KB Output is correct
22 Correct 1587 ms 8968 KB Output is correct
23 Correct 579 ms 18560 KB Output is correct
24 Correct 786 ms 11716 KB Output is correct
25 Correct 1324 ms 18824 KB Output is correct
26 Correct 1161 ms 19120 KB Output is correct
27 Correct 1046 ms 18372 KB Output is correct
28 Runtime error 919 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 332 KB Output is correct
3 Correct 1 ms 332 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 332 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 332 KB Output is correct
10 Correct 1 ms 332 KB Output is correct
11 Correct 1 ms 204 KB Output is correct
12 Correct 485 ms 13008 KB Output is correct
13 Correct 355 ms 13304 KB Output is correct
14 Correct 476 ms 10528 KB Output is correct
15 Correct 519 ms 10180 KB Output is correct
16 Correct 359 ms 7024 KB Output is correct
17 Correct 507 ms 10312 KB Output is correct
18 Correct 465 ms 9924 KB Output is correct
19 Correct 802 ms 15948 KB Output is correct
20 Correct 1270 ms 6292 KB Output is correct
21 Correct 296 ms 960 KB Output is correct
22 Correct 1517 ms 9036 KB Output is correct
23 Correct 512 ms 18504 KB Output is correct
24 Correct 772 ms 11716 KB Output is correct
25 Correct 1315 ms 18856 KB Output is correct
26 Correct 1111 ms 19152 KB Output is correct
27 Correct 1034 ms 18528 KB Output is correct
28 Runtime error 910 ms 256004 KB Execution killed with signal 9
29 Halted 0 ms 0 KB -