oj.uz

Submission #63789

# Submission time Handle Problem Language Result Execution time Memory
63789 2018-08-02T19:47:32 Z mohammad_kilani Game (IOI13_game) C++17
80 / 100
 10146 ms 257024 KB 
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
const int N = 22001 , M = N * 30 * 19 + 10, L = N * 30;
int r1 , r2 , c1 , c2 ,r , c , rowscnt = 0 , colscnt = 0, tmp1 , tmp2;
int nxt2[L][2];
int nxt1[L];
long long val , seg[M];
int nxt3[M][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_cols_3(int s,int e,int idx,int l,int r){
    if(l == -1 && r == -1)
        return;
    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((l != -1 && nxt3[l][1] != -1) || (r != -1 && nxt3[r][1] != -1)){
        if(nxt3[idx][1] == -1)
            nxt3[idx][1] = addcol();
        update_cols_3(((s+e) >> 1) + 1 , e,nxt3[idx][1],(l == -1 ? -1 : nxt3[l][1]) , (r == -1 ? -1 : nxt3[r][1]));
    }
    if((l != -1 && nxt3[l][0] != -1) || (r != -1 && nxt3[r][0] != -1)){
        if(nxt3[idx][0] == -1)
            nxt3[idx][0] = addcol();
        update_cols_3(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(nxt2[idx][0] == -1 || nxt2[idx][1] == -1) return;
    tmp1 = nxt2[idx][0];
    tmp2 = nxt2[idx][1];
    while((nxt2[tmp1][0] == -1) ^ (nxt2[tmp1][1] == -1)){
        if(nxt2[tmp1][0] == -1)
            tmp1 = nxt2[tmp1][1];
        else
            tmp1 = nxt2[tmp1][0];
    }
    if(tmp1 != -1)
        tmp1 = nxt1[tmp1];
    while((nxt2[tmp2][0] == -1) ^ (nxt2[tmp2][1] == -1)){
        if(nxt2[tmp2][0] == -1)
            tmp2 = nxt2[tmp2][1];
        else
            tmp2 = nxt2[tmp2][0];
    }
    if(tmp2 != -1)
        tmp2 = nxt1[tmp2];
    if(nxt1[idx] == -1){
        nxt1[idx] = addcol();
        update_cols_3(0, c , nxt1[idx], tmp1 , tmp2);
        return ;
    }
    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){
        if((nxt2[idx][0] == -1) ^ (nxt2[idx][1] == -1)){
            if(nxt2[idx][1] == -1)
                return get_rows(s,((s+e) >> 1),nxt2[idx][0]);
            return get_rows(((s+e) >> 1) + 1, e,nxt2[idx][1]);
        }
        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) {
    /*long double cur = sizeof(seg) + sizeof(nxt1) + sizeof(nxt2) + sizeof(nxt3);
    cur = cur / (1024.0 * 1024.0);
    cout << fixed << cur << endl;
    */
    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 2 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 3 ms 464 KB Output is correct
5 Correct 3 ms 476 KB Output is correct
6 Correct 4 ms 492 KB Output is correct
7 Correct 2 ms 556 KB Output is correct
8 Correct 2 ms 556 KB Output is correct
9 Correct 4 ms 568 KB Output is correct
10 Correct 3 ms 572 KB Output is correct
11 Correct 4 ms 576 KB Output is correct
12 Correct 3 ms 580 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 656 KB Output is correct
2 Correct 3 ms 656 KB Output is correct
3 Correct 3 ms 656 KB Output is correct
4 Correct 766 ms 13504 KB Output is correct
5 Correct 470 ms 15072 KB Output is correct
6 Correct 871 ms 15072 KB Output is correct
7 Correct 1088 ms 15072 KB Output is correct
8 Correct 638 ms 15072 KB Output is correct
9 Correct 1014 ms 15072 KB Output is correct
10 Correct 954 ms 15072 KB Output is correct
11 Correct 2 ms 15072 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 15072 KB Output is correct
2 Correct 5 ms 15072 KB Output is correct
3 Correct 3 ms 15072 KB Output is correct
4 Correct 4 ms 15072 KB Output is correct
5 Correct 3 ms 15072 KB Output is correct
6 Correct 4 ms 15072 KB Output is correct
7 Correct 3 ms 15072 KB Output is correct
8 Correct 3 ms 15072 KB Output is correct
9 Correct 3 ms 15072 KB Output is correct
10 Correct 3 ms 15072 KB Output is correct
11 Correct 3 ms 15072 KB Output is correct
12 Correct 1093 ms 16440 KB Output is correct
13 Correct 2965 ms 16440 KB Output is correct
14 Correct 383 ms 16440 KB Output is correct
15 Correct 3760 ms 16440 KB Output is correct
16 Correct 1152 ms 16440 KB Output is correct
17 Correct 1641 ms 16440 KB Output is correct
18 Correct 2851 ms 16440 KB Output is correct
19 Correct 2472 ms 16488 KB Output is correct
20 Correct 1919 ms 16488 KB Output is correct
21 Correct 3 ms 16488 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 16488 KB Output is correct
2 Correct 3 ms 16488 KB Output is correct
3 Correct 3 ms 16488 KB Output is correct
4 Correct 5 ms 16488 KB Output is correct
5 Correct 3 ms 16488 KB Output is correct
6 Correct 3 ms 16488 KB Output is correct
7 Correct 3 ms 16488 KB Output is correct
8 Correct 3 ms 16488 KB Output is correct
9 Correct 3 ms 16488 KB Output is correct
10 Correct 3 ms 16488 KB Output is correct
11 Correct 2 ms 16488 KB Output is correct
12 Correct 782 ms 16488 KB Output is correct
13 Correct 542 ms 16488 KB Output is correct
14 Correct 1029 ms 16488 KB Output is correct
15 Correct 1085 ms 16488 KB Output is correct
16 Correct 619 ms 16488 KB Output is correct
17 Correct 934 ms 16488 KB Output is correct
18 Correct 803 ms 16488 KB Output is correct
19 Correct 1300 ms 16488 KB Output is correct
20 Correct 3063 ms 16488 KB Output is correct
21 Correct 436 ms 16488 KB Output is correct
22 Correct 3658 ms 16488 KB Output is correct
23 Correct 1018 ms 16488 KB Output is correct
24 Correct 1572 ms 16488 KB Output is correct
25 Correct 2335 ms 16488 KB Output is correct
26 Correct 1949 ms 16488 KB Output is correct
27 Correct 2134 ms 16488 KB Output is correct
28 Correct 982 ms 53964 KB Output is correct
29 Correct 2577 ms 68288 KB Output is correct
30 Correct 8764 ms 68288 KB Output is correct
31 Correct 7879 ms 68288 KB Output is correct
32 Correct 732 ms 68288 KB Output is correct
33 Correct 1022 ms 68288 KB Output is correct
34 Correct 1478 ms 68288 KB Output is correct
35 Correct 2548 ms 68288 KB Output is correct
36 Correct 3923 ms 68288 KB Output is correct
37 Correct 3520 ms 68288 KB Output is correct
38 Correct 2810 ms 68288 KB Output is correct
39 Correct 2486 ms 68288 KB Output is correct
40 Correct 3 ms 68288 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 68288 KB Output is correct
2 Correct 10 ms 68288 KB Output is correct
3 Correct 4 ms 68288 KB Output is correct
4 Correct 3 ms 68288 KB Output is correct
5 Correct 1 ms 68288 KB Output is correct
6 Correct 3 ms 68288 KB Output is correct
7 Correct 3 ms 68288 KB Output is correct
8 Correct 3 ms 68288 KB Output is correct
9 Correct 3 ms 68288 KB Output is correct
10 Correct 3 ms 68288 KB Output is correct
11 Correct 4 ms 68288 KB Output is correct
12 Correct 706 ms 68288 KB Output is correct
13 Correct 527 ms 68288 KB Output is correct
14 Correct 834 ms 68288 KB Output is correct
15 Correct 973 ms 68288 KB Output is correct
16 Correct 632 ms 68288 KB Output is correct
17 Correct 939 ms 68288 KB Output is correct
18 Correct 738 ms 68288 KB Output is correct
19 Correct 1343 ms 68288 KB Output is correct
20 Correct 3046 ms 68288 KB Output is correct
21 Correct 423 ms 68288 KB Output is correct
22 Correct 3904 ms 68288 KB Output is correct
23 Correct 1091 ms 68288 KB Output is correct
24 Correct 1455 ms 68288 KB Output is correct
25 Correct 2467 ms 68288 KB Output is correct
26 Correct 2145 ms 68288 KB Output is correct
27 Correct 1890 ms 68288 KB Output is correct
28 Correct 1006 ms 68288 KB Output is correct
29 Correct 2731 ms 68288 KB Output is correct
30 Correct 7881 ms 68288 KB Output is correct
31 Correct 8267 ms 68288 KB Output is correct
32 Correct 733 ms 68288 KB Output is correct
33 Correct 1006 ms 68288 KB Output is correct
34 Correct 1746 ms 104596 KB Output is correct
35 Correct 2312 ms 104596 KB Output is correct
36 Correct 4179 ms 125308 KB Output is correct
37 Correct 3724 ms 136052 KB Output is correct
38 Correct 3709 ms 146184 KB Output is correct
39 Correct 1362 ms 203132 KB Output is correct
40 Correct 4681 ms 245300 KB Output is correct
41 Correct 10146 ms 245300 KB Output is correct
42 Correct 9629 ms 245300 KB Output is correct
43 Runtime error 1946 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.
44 Halted 0 ms 0 KB -