oj.uz

Submission #599173

# Submission time Handle Problem Language Result Execution time Memory
599173 2022-07-19T11:18:48 Z alirezasamimi100 Game (IOI13_game) C++17
63 / 100
 1552 ms 256000 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
using ll = long long int;

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

struct n1{
    n1 *lc,*rc;
    ll x;
    n1(){
        lc=rc=nullptr;
        x=0;
    }
};
struct n2{
    n2 *lc,*rc;
    n1 *x;
    n2(){
        lc=rc=nullptr;
        x=new n1;
    }
} *rt=new n2;

int n,m;

void upd1(n1 *v, int l, int r, int p, ll x){
    if(r-l==1){
        v->x=x;
        return;
    }
    int m=(l+r)>>1;
    if(p<m){
        if(!v->lc) v->lc=new n1;
        upd1(v->lc,l,m,p,x);
    }else{
        if(!v->rc) v->rc=new n1;
        upd1(v->rc,m,r,p,x);
    }
    v->x=0;
    if(v->lc) v->x=gcd2(v->x,v->lc->x);
    if(v->rc) v->x=gcd2(v->x,v->rc->x);
}

ll get1(n1 *v, int l, int r, int tl, int tr){
    if(l>=tr || tl>=r || tl>=tr) return 0;
    if(l>=tl && r<=tr) return v->x;
    int m=(l+r)>>1;
    ll ans=0;
    if(v->lc) ans=gcd2(ans,get1(v->lc,l,m,tl,tr));
    if(v->rc) ans=gcd2(ans,get1(v->rc,m,r,tl,tr));
    return ans;
}

void upd2(n2 *v, int l, int r, int p, int q, ll x){
    if(r-l==1){
        upd1(v->x,0,m,q,x);
        return;
    }
    int m=(l+r)>>1;
    if(p<m){
        if(!v->lc) v->lc=new n2;
        upd2(v->lc,l,m,p,q,x);
    }else{
        if(!v->rc) v->rc=new n2;
        upd2(v->rc,m,r,p,q,x);
    }
    ll y=0;
    if(v->lc) y=gcd2(y,get1(v->lc->x,0,::m,q,q+1));
    if(v->rc) y=gcd2(y,get1(v->rc->x,0,::m,q,q+1));
    upd1(v->x,0,::m,q,y);
}

ll get2(n2 *v, int l, int r, int tl, int tr, int tp, int tq){
    if(l>=tr || tl>=r || tl>=tr) return 0;
    if(l>=tl && r<=tr) return get1(v->x,0,m,tp,tq);
    int m=(l+r)>>1;
    ll ans=0;
    if(v->lc) ans=gcd2(ans,get2(v->lc,l,m,tl,tr,tp,tq));
    if(v->rc) ans=gcd2(ans,get2(v->rc,m,r,tl,tr,tp,tq));
    return ans;
}

void init(int R, int C) {
    n=R;
    m=C;
}

void update(int p, int q, long long k) {
    upd2(rt,0,n,p,q,k);
}

long long calculate(int p, int q, int u, int v) {
    return get2(rt,0,n,p,u+1,q,v+1);
}

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 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 0 ms 304 KB Output is correct
5 Correct 1 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 304 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 304 KB Output is correct
11 Correct 1 ms 212 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 1 ms 300 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 1 ms 212 KB Output is correct
4 Correct 455 ms 17024 KB Output is correct
5 Correct 347 ms 16920 KB Output is correct
6 Correct 395 ms 14488 KB Output is correct
7 Correct 414 ms 14188 KB Output is correct
8 Correct 320 ms 10904 KB Output is correct
9 Correct 408 ms 14404 KB Output is correct
10 Correct 378 ms 13844 KB Output is correct
11 Correct 1 ms 304 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 212 KB Output is correct
2 Correct 1 ms 296 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 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 0 ms 212 KB Output is correct
9 Correct 1 ms 300 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 774 ms 20028 KB Output is correct
13 Correct 1122 ms 10288 KB Output is correct
14 Correct 233 ms 5580 KB Output is correct
15 Correct 1323 ms 13212 KB Output is correct
16 Correct 206 ms 22476 KB Output is correct
17 Correct 630 ms 16496 KB Output is correct
18 Correct 1101 ms 24072 KB Output is correct
19 Correct 999 ms 23940 KB Output is correct
20 Correct 914 ms 23452 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 1 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 1 ms 212 KB Output is correct
5 Correct 0 ms 296 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 304 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 450 ms 16932 KB Output is correct
13 Correct 317 ms 16884 KB Output is correct
14 Correct 390 ms 14524 KB Output is correct
15 Correct 498 ms 14184 KB Output is correct
16 Correct 290 ms 10784 KB Output is correct
17 Correct 427 ms 14240 KB Output is correct
18 Correct 414 ms 13832 KB Output is correct
19 Correct 717 ms 19972 KB Output is correct
20 Correct 1132 ms 10096 KB Output is correct
21 Correct 257 ms 5676 KB Output is correct
22 Correct 1355 ms 13212 KB Output is correct
23 Correct 195 ms 22468 KB Output is correct
24 Correct 683 ms 16336 KB Output is correct
25 Correct 1091 ms 23772 KB Output is correct
26 Correct 1035 ms 23960 KB Output is correct
27 Correct 937 ms 23380 KB Output is correct
28 Correct 843 ms 256000 KB Output is correct
29 Runtime error 1552 ms 256000 KB Execution killed with signal 9
30 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 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 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 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 478 ms 16972 KB Output is correct
13 Correct 355 ms 16920 KB Output is correct
14 Correct 418 ms 14400 KB Output is correct
15 Correct 489 ms 14324 KB Output is correct
16 Correct 305 ms 10820 KB Output is correct
17 Correct 415 ms 14316 KB Output is correct
18 Correct 458 ms 13944 KB Output is correct
19 Correct 751 ms 19964 KB Output is correct
20 Correct 1134 ms 10100 KB Output is correct
21 Correct 238 ms 5584 KB Output is correct
22 Correct 1323 ms 13240 KB Output is correct
23 Correct 210 ms 22348 KB Output is correct
24 Correct 740 ms 16232 KB Output is correct
25 Correct 1150 ms 23740 KB Output is correct
26 Correct 1008 ms 24020 KB Output is correct
27 Correct 878 ms 23308 KB Output is correct
28 Correct 785 ms 256000 KB Output is correct
29 Runtime error 1528 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -