oj.uz

Submission #599211

# Submission time Handle Problem Language Result Execution time Memory
599211 2022-07-19T11:41:20 Z alirezasamimi100 Game (IOI13_game) C++17
63 / 100
 1553 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=gcd(v->x,v->lc->x);
    if(v->rc) v->x=gcd(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=gcd(ans,get1(v->lc,l,m,tl,tr));
    if(v->rc) ans=gcd(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=gcd(y,get1(v->lc->x,0,::m,q,q+1));
    if(v->rc) y=gcd(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=gcd(ans,get2(v->lc,l,m,tl,tr,tp,tq));
    if(v->rc) ans=gcd(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 1 ms 212 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 304 KB Output is correct
4 Correct 1 ms 212 KB Output is correct
5 Correct 1 ms 304 KB Output is correct
6 Correct 1 ms 300 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 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 300 KB Output is correct
12 Correct 1 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 1 ms 296 KB Output is correct
3 Correct 1 ms 244 KB Output is correct
4 Correct 491 ms 17116 KB Output is correct
5 Correct 356 ms 16780 KB Output is correct
6 Correct 465 ms 14392 KB Output is correct
7 Correct 513 ms 14152 KB Output is correct
8 Correct 424 ms 10864 KB Output is correct
9 Correct 511 ms 14280 KB Output is correct
10 Correct 548 ms 13932 KB Output is correct
11 Correct 1 ms 212 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 296 KB Output is correct
2 Correct 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 296 KB Output is correct
5 Correct 0 ms 300 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 340 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 304 KB Output is correct
12 Correct 764 ms 19928 KB Output is correct
13 Correct 1322 ms 9988 KB Output is correct
14 Correct 249 ms 5548 KB Output is correct
15 Correct 1513 ms 13088 KB Output is correct
16 Correct 227 ms 22436 KB Output is correct
17 Correct 676 ms 16292 KB Output is correct
18 Correct 1137 ms 23848 KB Output is correct
19 Correct 1031 ms 24088 KB Output is correct
20 Correct 909 ms 23380 KB Output is correct
21 Correct 1 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 2 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 300 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 340 KB Output is correct
12 Correct 503 ms 16968 KB Output is correct
13 Correct 394 ms 16908 KB Output is correct
14 Correct 401 ms 14348 KB Output is correct
15 Correct 444 ms 14140 KB Output is correct
16 Correct 339 ms 10800 KB Output is correct
17 Correct 431 ms 14220 KB Output is correct
18 Correct 429 ms 13884 KB Output is correct
19 Correct 786 ms 19952 KB Output is correct
20 Correct 1319 ms 10080 KB Output is correct
21 Correct 328 ms 5548 KB Output is correct
22 Correct 1553 ms 13256 KB Output is correct
23 Correct 200 ms 22328 KB Output is correct
24 Correct 639 ms 16336 KB Output is correct
25 Correct 1176 ms 23940 KB Output is correct
26 Correct 956 ms 24008 KB Output is correct
27 Correct 911 ms 23500 KB Output is correct
28 Correct 826 ms 256000 KB Output is correct
29 Runtime error 1391 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 0 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 1 ms 292 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 340 KB Output is correct
12 Correct 462 ms 16956 KB Output is correct
13 Correct 371 ms 16760 KB Output is correct
14 Correct 384 ms 14500 KB Output is correct
15 Correct 425 ms 14132 KB Output is correct
16 Correct 291 ms 10852 KB Output is correct
17 Correct 464 ms 14356 KB Output is correct
18 Correct 372 ms 13868 KB Output is correct
19 Correct 737 ms 19924 KB Output is correct
20 Correct 1144 ms 10060 KB Output is correct
21 Correct 241 ms 5540 KB Output is correct
22 Correct 1341 ms 13100 KB Output is correct
23 Correct 197 ms 22364 KB Output is correct
24 Correct 644 ms 16100 KB Output is correct
25 Correct 1083 ms 23112 KB Output is correct
26 Correct 908 ms 23356 KB Output is correct
27 Correct 875 ms 22688 KB Output is correct
28 Correct 830 ms 256000 KB Output is correct
29 Runtime error 1430 ms 256000 KB Execution killed with signal 9
30 Halted 0 ms 0 KB -