oj.uz

Submission #56848

# Submission time Handle Problem Language Result Execution time Memory
56848 2018-07-12T20:24:20 Z hamzqq9 Game (IOI13_game) C++14
63 / 100
 6621 ms 257024 KB 
#include "game.h"
#include<bits/stdc++.h>
using namespace std;

#define ll long long
#define MAXQ 10005
#define orta ((bas+son)/2)

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

struct SEG2 {

    int L,R;

    ll GCD;

} S2[MAXQ*32*32];

struct SEG1 {

    int U,D;

    int SG2;

} S1[MAXQ*32];

int total2,total1,R,C;

ll get2(int node,int bas,int son,int Q,int V) {

    if(!node || bas>V || son<Q) return 0;

    if(bas>=Q && son<=V) return S2[node].GCD;

    return gcd2(get2(S2[node].L,bas,orta,Q,V),get2(S2[node].R,orta+1,son,Q,V));

}

ll get1(int node,int bas,int son,int P,int Q,int U,int V) {

    if(!node || bas>U || son<P) return 0;

    if(bas>=P && son<=U) {

        if(!S1[node].SG2) return 0;

        return get2(S1[node].SG2,0,C-1,Q,V);

    }

    return gcd2(get1(S1[node].U,bas,orta,P,Q,U,V),get1(S1[node].D,orta+1,son,P,Q,U,V));
 
}

void up2(int node,int bas,int son,int Q,ll K) {

    if(bas>Q || son<Q) return ;

    if(bas==Q && son==Q) {

        S2[node].GCD=K;

        return ;

    }

    if(orta>=Q) {

        if(!S2[node].L) {

            total2++;

            S2[node].L=total2;

        }
        
        up2(S2[node].L,bas,orta,Q,K);
    
    }
    else {
    
        if(!S2[node].R) {

            total2++;

            S2[node].R=total2;

        }

        up2(S2[node].R,orta+1,son,Q,K);
    
    }

    S2[node].GCD=gcd2(S2[S2[node].L].GCD,S2[S2[node].R].GCD);

}

void up1(int node,int bas,int son,int P,int Q,ll K) {

    if(bas==P && son==P) {

        if(!S1[node].SG2) {

            total2++;

            S1[node].SG2=total2;

        }

        up2(S1[node].SG2,0,C-1,Q,K);

        return ;

    }

    if(orta>=P) {

        if(!S1[node].U) {

            total1++;

            S1[node].U=total1;

        }
        
        up1(S1[node].U,bas,orta,P,Q,K);

    }
    else {

        if(!S1[node].D) {

            total1++;

            S1[node].D=total1;

        }   

        up1(S1[node].D,orta+1,son,P,Q,K);
   
    }

    if(!S1[node].SG2) {

        total2++;
        S1[node].SG2=total2;

    }

    K=gcd2(get2(S1[S1[node].U].SG2,0,C-1,Q,Q),get2(S1[S1[node].D].SG2,0,C-1,Q,Q));

    up2(S1[node].SG2,0,C-1,Q,K);

}

void init(int R, int C) {
    
    total1=1;

    ::R=R;
    ::C=C;

}

void update(int P, int Q, long long K) {

    up1(1,0,R-1,P,Q,K);

}

long long calculate(int P, int Q, int U, int V) {

    return get1(1,0,R-1,P,Q,U,V);

}
/*
#include <stdio.h>
#include <stdlib.h>
#include "game.h"

#define fail(s, x...) do { \
        fprintf(stderr, s "\n", ## x); \
        exit(1); \
    } while(0)

#define MAX_SIZE 1000000000
#define MAX_N 272000

int main() {
    int R, C, N;
    int P, Q, U, V;
    long long K;
    int i, type;
    int res;

    FILE *f = fopen("game.in", "r");
    if (!f)
        fail("Failed to open input file.");

    res = fscanf(f, "%d", &R);
    res = fscanf(f, "%d", &C);
    res = fscanf(f, "%d", &N);

    init(R, C);

    for (i = 0; i < N; i++) {
        res = fscanf(f, "%d", &type);
        if (type == 1) {
            res = fscanf(f, "%d%d%lld", &P, &Q, &K);
            update(P, Q, K);
        } else if (type == 2) {
            res = fscanf(f, "%d%d%d%d", &P, &Q, &U, &V);
            printf("QUERY----> %lld\n", calculate(P, Q, U, V));
        } else
            fail("Invalid action type in input file.");
    }
    fclose(f);

    return 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 248 KB Output is correct
2 Correct 4 ms 488 KB Output is correct
3 Correct 4 ms 568 KB Output is correct
4 Correct 3 ms 568 KB Output is correct
5 Correct 3 ms 568 KB Output is correct
6 Correct 6 ms 568 KB Output is correct
7 Correct 3 ms 568 KB Output is correct
8 Correct 2 ms 568 KB Output is correct
9 Correct 3 ms 684 KB Output is correct
10 Correct 2 ms 684 KB Output is correct
11 Correct 3 ms 684 KB Output is correct
12 Correct 3 ms 684 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 684 KB Output is correct
2 Correct 2 ms 684 KB Output is correct
3 Correct 3 ms 684 KB Output is correct
4 Correct 919 ms 11036 KB Output is correct
5 Correct 673 ms 15160 KB Output is correct
6 Correct 904 ms 16744 KB Output is correct
7 Correct 1057 ms 21104 KB Output is correct
8 Correct 652 ms 24304 KB Output is correct
9 Correct 997 ms 30068 KB Output is correct
10 Correct 891 ms 30344 KB Output is correct
11 Correct 2 ms 30344 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 30344 KB Output is correct
2 Correct 3 ms 30344 KB Output is correct
3 Correct 4 ms 30344 KB Output is correct
4 Correct 3 ms 30344 KB Output is correct
5 Correct 2 ms 30344 KB Output is correct
6 Correct 4 ms 30344 KB Output is correct
7 Correct 3 ms 30344 KB Output is correct
8 Correct 3 ms 30344 KB Output is correct
9 Correct 3 ms 30344 KB Output is correct
10 Correct 3 ms 30344 KB Output is correct
11 Correct 3 ms 30344 KB Output is correct
12 Correct 1363 ms 35280 KB Output is correct
13 Correct 3010 ms 35280 KB Output is correct
14 Correct 485 ms 35280 KB Output is correct
15 Correct 3401 ms 41840 KB Output is correct
16 Correct 361 ms 50724 KB Output is correct
17 Correct 1738 ms 52564 KB Output is correct
18 Correct 3057 ms 61188 KB Output is correct
19 Correct 2674 ms 66568 KB Output is correct
20 Correct 2487 ms 71216 KB Output is correct
21 Correct 3 ms 71216 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 71216 KB Output is correct
2 Correct 3 ms 71216 KB Output is correct
3 Correct 3 ms 71216 KB Output is correct
4 Correct 3 ms 71216 KB Output is correct
5 Correct 2 ms 71216 KB Output is correct
6 Correct 3 ms 71216 KB Output is correct
7 Correct 3 ms 71216 KB Output is correct
8 Correct 2 ms 71216 KB Output is correct
9 Correct 3 ms 71216 KB Output is correct
10 Correct 2 ms 71216 KB Output is correct
11 Correct 3 ms 71216 KB Output is correct
12 Correct 923 ms 71216 KB Output is correct
13 Correct 730 ms 71216 KB Output is correct
14 Correct 1032 ms 71216 KB Output is correct
15 Correct 1055 ms 71216 KB Output is correct
16 Correct 694 ms 71216 KB Output is correct
17 Correct 1053 ms 71216 KB Output is correct
18 Correct 771 ms 71216 KB Output is correct
19 Correct 1429 ms 71724 KB Output is correct
20 Correct 2927 ms 71724 KB Output is correct
21 Correct 463 ms 71724 KB Output is correct
22 Correct 3262 ms 79896 KB Output is correct
23 Correct 402 ms 88676 KB Output is correct
24 Correct 1466 ms 90556 KB Output is correct
25 Correct 1916 ms 99264 KB Output is correct
26 Correct 1608 ms 104684 KB Output is correct
27 Correct 1476 ms 106868 KB Output is correct
28 Correct 1138 ms 218264 KB Output is correct
29 Correct 2686 ms 241556 KB Output is correct
30 Correct 6492 ms 241556 KB Output is correct
31 Correct 6621 ms 241556 KB Output is correct
32 Correct 939 ms 241556 KB Output is correct
33 Correct 1130 ms 241556 KB Output is correct
34 Runtime error 827 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.
35 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 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.
2 Halted 0 ms 0 KB -