oj.uz

Submission #63784

# Submission time Handle Problem Language Result Execution time Memory
63784 2018-08-02T18:52:09 Z mohammad_kilani Game (IOI13_game) C++17
80 / 100
 9866 ms 257024 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 15001 ;
int r1 , r2 , c1 , c2 ,r , c , rowscnt = 0 , colscnt = 0, tmp1 , tmp2;
int nxt2[N * 30][2];
int nxt1[N * 30];
long long val , seg[N * 30 * 30];
int nxt3[N * 30 * 30][2];

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 4 ms 576 KB Output is correct
3 Correct 4 ms 652 KB Output is correct
4 Correct 3 ms 652 KB Output is correct
5 Correct 3 ms 652 KB Output is correct
6 Correct 4 ms 652 KB Output is correct
7 Correct 2 ms 652 KB Output is correct
8 Correct 3 ms 652 KB Output is correct
9 Correct 4 ms 652 KB Output is correct
10 Correct 3 ms 652 KB Output is correct
11 Correct 2 ms 652 KB Output is correct
12 Correct 3 ms 652 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 652 KB Output is correct
2 Correct 3 ms 652 KB Output is correct
3 Correct 3 ms 652 KB Output is correct
4 Correct 837 ms 13372 KB Output is correct
5 Correct 518 ms 17744 KB Output is correct
6 Correct 1002 ms 17744 KB Output is correct
7 Correct 1171 ms 17744 KB Output is correct
8 Correct 663 ms 17744 KB Output is correct
9 Correct 1083 ms 17744 KB Output is correct
10 Correct 906 ms 17744 KB Output is correct
11 Correct 3 ms 17744 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 17744 KB Output is correct
2 Correct 3 ms 17744 KB Output is correct
3 Correct 4 ms 17744 KB Output is correct
4 Correct 3 ms 17744 KB Output is correct
5 Correct 3 ms 17744 KB Output is correct
6 Correct 3 ms 17744 KB Output is correct
7 Correct 4 ms 17744 KB Output is correct
8 Correct 3 ms 17744 KB Output is correct
9 Correct 3 ms 17744 KB Output is correct
10 Correct 3 ms 17744 KB Output is correct
11 Correct 3 ms 17744 KB Output is correct
12 Correct 1222 ms 20864 KB Output is correct
13 Correct 3329 ms 20864 KB Output is correct
14 Correct 433 ms 20864 KB Output is correct
15 Correct 3673 ms 20864 KB Output is correct
16 Correct 1239 ms 20864 KB Output is correct
17 Correct 1705 ms 20864 KB Output is correct
18 Correct 2749 ms 20864 KB Output is correct
19 Correct 2298 ms 20960 KB Output is correct
20 Correct 2202 ms 20960 KB Output is correct
21 Correct 3 ms 20960 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 20960 KB Output is correct
2 Correct 3 ms 20960 KB Output is correct
3 Correct 4 ms 20960 KB Output is correct
4 Correct 3 ms 20960 KB Output is correct
5 Correct 3 ms 20960 KB Output is correct
6 Correct 3 ms 20960 KB Output is correct
7 Correct 2 ms 20960 KB Output is correct
8 Correct 2 ms 20960 KB Output is correct
9 Correct 3 ms 20960 KB Output is correct
10 Correct 4 ms 20960 KB Output is correct
11 Correct 3 ms 20960 KB Output is correct
12 Correct 736 ms 20960 KB Output is correct
13 Correct 526 ms 20960 KB Output is correct
14 Correct 1006 ms 20960 KB Output is correct
15 Correct 1192 ms 20960 KB Output is correct
16 Correct 607 ms 20960 KB Output is correct
17 Correct 1246 ms 20960 KB Output is correct
18 Correct 958 ms 20960 KB Output is correct
19 Correct 1395 ms 20960 KB Output is correct
20 Correct 3377 ms 20960 KB Output is correct
21 Correct 524 ms 20960 KB Output is correct
22 Correct 3484 ms 20960 KB Output is correct
23 Correct 1060 ms 20960 KB Output is correct
24 Correct 1773 ms 20960 KB Output is correct
25 Correct 3172 ms 20960 KB Output is correct
26 Correct 2346 ms 21088 KB Output is correct
27 Correct 2242 ms 21088 KB Output is correct
28 Correct 1207 ms 136284 KB Output is correct
29 Correct 2804 ms 161464 KB Output is correct
30 Correct 9866 ms 161464 KB Output is correct
31 Correct 9223 ms 161464 KB Output is correct
32 Correct 846 ms 161464 KB Output is correct
33 Correct 1284 ms 161464 KB Output is correct
34 Correct 1852 ms 197876 KB Output is correct
35 Correct 2460 ms 197876 KB Output is correct
36 Correct 4594 ms 218684 KB Output is correct
37 Correct 3516 ms 229452 KB Output is correct
38 Correct 3364 ms 239524 KB Output is correct
39 Correct 3010 ms 239524 KB Output is correct
40 Correct 2 ms 239524 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 239524 KB Output is correct
2 Correct 3 ms 239524 KB Output is correct
3 Correct 3 ms 239524 KB Output is correct
4 Correct 3 ms 239524 KB Output is correct
5 Correct 3 ms 239524 KB Output is correct
6 Correct 3 ms 239524 KB Output is correct
7 Correct 3 ms 239524 KB Output is correct
8 Correct 3 ms 239524 KB Output is correct
9 Correct 3 ms 239524 KB Output is correct
10 Correct 3 ms 239524 KB Output is correct
11 Correct 3 ms 239524 KB Output is correct
12 Correct 701 ms 239524 KB Output is correct
13 Correct 478 ms 239524 KB Output is correct
14 Correct 835 ms 239524 KB Output is correct
15 Correct 1209 ms 239524 KB Output is correct
16 Correct 740 ms 239524 KB Output is correct
17 Correct 1317 ms 239524 KB Output is correct
18 Correct 1002 ms 239524 KB Output is correct
19 Correct 1337 ms 239524 KB Output is correct
20 Correct 3227 ms 239524 KB Output is correct
21 Correct 449 ms 239524 KB Output is correct
22 Correct 3930 ms 239524 KB Output is correct
23 Correct 1058 ms 239524 KB Output is correct
24 Correct 1509 ms 239524 KB Output is correct
25 Correct 2870 ms 239524 KB Output is correct
26 Correct 2546 ms 239524 KB Output is correct
27 Correct 2120 ms 239524 KB Output is correct
28 Correct 1234 ms 239524 KB Output is correct
29 Runtime error 2684 ms 257024 KB Memory limit exceeded: We have a known bug that the memory usage is measured incorrectly (possibly because of Meltdown/Spectre patch), so your solution may be correct. Please submit again. Sorry for the inconvenience.
30 Halted 0 ms 0 KB -