oj.uz

Submission #63783

# Submission time Handle Problem Language Result Execution time Memory
63783 2018-08-02T18:48:19 Z mohammad_kilani Game (IOI13_game) C++17
63 / 100
 5257 ms 243752 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 10001 ;
int r1 , r2 , c1 , c2 ,r , c , nxt1[N * 30], rowscnt = 0 , colscnt = 0 , F2 , tmp1 , tmp2;
short nxt2[N * 30][2];
long long val , seg[N * 30 * 30];
int nxt3[N * 30 * 30][2];
bool F;

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

inline int addrow(){
    nxt1[rowscnt] = -1;
    nxt2[rowscnt][0] = nxt2[rowscnt][1] = -1;
    return rowscnt++;
}

inline int addcol(){
    seg[colscnt] = 0;
    nxt3[colscnt][0] = nxt3[colscnt][1] = -1;
    return colscnt++;
}

void update_cols(int s,int e,int idx){
    if(s == e){
        seg[idx] = val;
        return;
    }
    if(c1 > ((s + e) >> 1)){
        if(nxt3[idx][1] == -1)
            nxt3[idx][1] = addcol();
        update_cols(((s+e) >> 1) + 1, e, nxt3[idx][1]);
    }
    else{
         if(nxt3[idx][0] == -1)
            nxt3[idx][0] = addcol();
        update_cols(s,((s+e) >> 1),nxt3[idx][0]);
    }
    seg[idx] = 0;
    if(nxt3[idx][0] != -1) seg[idx] = gcd2(seg[idx],seg[nxt3[idx][0]]);
    if(nxt3[idx][1] != -1) seg[idx] = gcd2(seg[idx],seg[nxt3[idx][1]]);
}

void update_cols_2(int s,int e,int idx,int l,int r){
    if(s == e){
        seg[idx] = 0;
        if(l != -1) seg[idx] = gcd2(seg[idx],seg[l]);
        if(r != -1) seg[idx] = gcd2(seg[idx],seg[r]);
        return ;
    }
    if(c1 > ((s + e) >> 1)){
        if(nxt3[idx][1] == -1)
            nxt3[idx][1] = addcol();
        update_cols_2(((s+e) >> 1) + 1 , e,nxt3[idx][1],(l == -1 ? -1 : nxt3[l][1]) , (r == -1 ? -1 : nxt3[r][1]));
    }
    else{
        if(nxt3[idx][0] == -1)
            nxt3[idx][0] = addcol();
        update_cols_2(s , ((s+e) >> 1) , nxt3[idx][0],(l == -1 ? -1 : nxt3[l][0]) , (r == -1 ? -1 : nxt3[r][0]));
    }
    seg[idx] = 0;
    if(nxt3[idx][0] != -1) seg[idx] = gcd2(seg[idx],seg[nxt3[idx][0]]);
    if(nxt3[idx][1] != -1) seg[idx] = gcd2(seg[idx],seg[nxt3[idx][1]]);

}

void update_rows(int s,int e,int idx){
    if(s == e){
        if(nxt1[idx] == -1)
            nxt1[idx] = addcol();
        update_cols(0 , c , nxt1[idx]);
        return;
    }
    if(r1 > ((s + e) >> 1)){
        if(nxt2[idx][1] == -1)
            nxt2[idx][1] = addrow();
        update_rows(((s+e) >> 1) + 1, e,nxt2[idx][1]);
    }
    else{
        if(nxt2[idx][0] == -1)
            nxt2[idx][0] = addrow();
        update_rows(s , ((s+e) >> 1), nxt2[idx][0]);
    }
    if(nxt1[idx] == -1)
            nxt1[idx] = addcol();
    tmp1 = nxt2[idx][0];
    tmp2 = nxt2[idx][1];
    if(tmp1 != -1)
        tmp1 = nxt1[tmp1];
    if(tmp2 != -1)
        tmp2 = nxt1[tmp2];
    update_cols_2(0 , c , nxt1[idx] , tmp1 , tmp2);
}

long long get_cols(int s,int e,int idx){
    if(s > c2 || e < c1 || idx == -1)
        return 0;
    if(s >= c1 && e <= c2)
        return seg[idx];
    return gcd2(get_cols(s,((s+e) >> 1),nxt3[idx][0]),get_cols(((s+e) >> 1) + 1, e,nxt3[idx][1]));
}

long long get_rows(int s,int e,int idx){
    if(s > r2 || e < r1 || idx == -1)
        return 0;
    if(s >= r1 && e <= r2){
        return get_cols(0 , c , nxt1[idx]);
    }
    return gcd2(get_rows(s,((s+e) >> 1),nxt2[idx][0]),get_rows(((s+e) >> 1) + 1, e,nxt2[idx][1]));
}


void init(int R, int C) {
    r = R ;
    c = C;
    addrow();
}

void update(int P, int Q, long long K) {
    r1 = P;
    c1 = Q;
    val = K;
    update_rows(0 , r , 0);
}

long long calculate(int P, int Q, int U, int V) {
    r1 = P;
    r2 = U;
    c1 = Q;
    c2 = V;
    return get_rows(0 , r , 0);
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
  int res;
      ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 376 KB Output is correct
2 Correct 3 ms 376 KB Output is correct
3 Correct 3 ms 412 KB Output is correct
4 Correct 2 ms 416 KB Output is correct
5 Correct 3 ms 496 KB Output is correct
6 Correct 3 ms 556 KB Output is correct
7 Correct 3 ms 560 KB Output is correct
8 Correct 4 ms 640 KB Output is correct
9 Correct 3 ms 644 KB Output is correct
10 Correct 3 ms 644 KB Output is correct
11 Correct 3 ms 652 KB Output is correct
12 Correct 4 ms 656 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 660 KB Output is correct
2 Correct 3 ms 664 KB Output is correct
3 Correct 3 ms 664 KB Output is correct
4 Correct 828 ms 13476 KB Output is correct
5 Correct 578 ms 17616 KB Output is correct
6 Correct 1002 ms 19372 KB Output is correct
7 Correct 1209 ms 23672 KB Output is correct
8 Correct 685 ms 26756 KB Output is correct
9 Correct 1089 ms 32644 KB Output is correct
10 Correct 1016 ms 36896 KB Output is correct
11 Correct 4 ms 36896 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 36896 KB Output is correct
2 Correct 3 ms 36896 KB Output is correct
3 Correct 4 ms 36896 KB Output is correct
4 Correct 3 ms 36896 KB Output is correct
5 Correct 2 ms 36896 KB Output is correct
6 Correct 3 ms 36896 KB Output is correct
7 Correct 3 ms 36896 KB Output is correct
8 Correct 3 ms 36896 KB Output is correct
9 Correct 3 ms 36896 KB Output is correct
10 Correct 4 ms 36896 KB Output is correct
11 Correct 4 ms 36896 KB Output is correct
12 Correct 1367 ms 45672 KB Output is correct
13 Correct 3214 ms 45672 KB Output is correct
14 Correct 408 ms 45672 KB Output is correct
15 Correct 3556 ms 53648 KB Output is correct
16 Correct 1098 ms 62552 KB Output is correct
17 Correct 1629 ms 64376 KB Output is correct
18 Correct 2942 ms 73148 KB Output is correct
19 Correct 2348 ms 78616 KB Output is correct
20 Correct 2121 ms 83456 KB Output is correct
21 Correct 3 ms 83456 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 83456 KB Output is correct
2 Correct 4 ms 83456 KB Output is correct
3 Correct 5 ms 83456 KB Output is correct
4 Correct 3 ms 83456 KB Output is correct
5 Correct 3 ms 83456 KB Output is correct
6 Correct 2 ms 83456 KB Output is correct
7 Correct 3 ms 83456 KB Output is correct
8 Correct 3 ms 83456 KB Output is correct
9 Correct 3 ms 83456 KB Output is correct
10 Correct 4 ms 83456 KB Output is correct
11 Correct 5 ms 83456 KB Output is correct
12 Correct 943 ms 86824 KB Output is correct
13 Correct 547 ms 91128 KB Output is correct
14 Correct 934 ms 92796 KB Output is correct
15 Correct 1138 ms 97112 KB Output is correct
16 Correct 675 ms 100200 KB Output is correct
17 Correct 1028 ms 105972 KB Output is correct
18 Correct 1046 ms 110400 KB Output is correct
19 Correct 1265 ms 118956 KB Output is correct
20 Correct 3073 ms 118956 KB Output is correct
21 Correct 419 ms 118956 KB Output is correct
22 Correct 3566 ms 118956 KB Output is correct
23 Correct 966 ms 127144 KB Output is correct
24 Correct 1542 ms 128824 KB Output is correct
25 Correct 2850 ms 137652 KB Output is correct
26 Correct 2309 ms 142924 KB Output is correct
27 Correct 2192 ms 147828 KB Output is correct
28 Incorrect 5257 ms 208380 KB Output isn't correct
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 208380 KB Output is correct
2 Correct 4 ms 208380 KB Output is correct
3 Correct 3 ms 208380 KB Output is correct
4 Correct 2 ms 208380 KB Output is correct
5 Correct 3 ms 208380 KB Output is correct
6 Correct 4 ms 208380 KB Output is correct
7 Correct 3 ms 208380 KB Output is correct
8 Correct 3 ms 208380 KB Output is correct
9 Correct 4 ms 208380 KB Output is correct
10 Correct 3 ms 208380 KB Output is correct
11 Correct 4 ms 208380 KB Output is correct
12 Correct 854 ms 208380 KB Output is correct
13 Correct 611 ms 208380 KB Output is correct
14 Correct 1002 ms 208380 KB Output is correct
15 Correct 1151 ms 208380 KB Output is correct
16 Correct 628 ms 208380 KB Output is correct
17 Correct 966 ms 208380 KB Output is correct
18 Correct 858 ms 208380 KB Output is correct
19 Correct 1292 ms 208380 KB Output is correct
20 Correct 3254 ms 208380 KB Output is correct
21 Correct 518 ms 208380 KB Output is correct
22 Correct 3589 ms 208380 KB Output is correct
23 Correct 1042 ms 208380 KB Output is correct
24 Correct 1606 ms 208380 KB Output is correct
25 Correct 2800 ms 208380 KB Output is correct
26 Correct 2370 ms 208380 KB Output is correct
27 Correct 2242 ms 208380 KB Output is correct
28 Incorrect 5086 ms 243752 KB Output isn't correct
29 Halted 0 ms 0 KB -