oj.uz

Submission #56845

# Submission time Handle Problem Language Result Execution time Memory
56845 2018-07-12T20:17:31 Z hamzqq9 Game (IOI13_game) C++14
63 / 100
 3830 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(!S2[node].L) {

        total2++;

        S2[node].L=total2;

    }

    if(!S2[node].R) {

        total2++;

        S2[node].R=total2;

    }

    up2(S2[node].L,bas,orta,Q,K);
    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) return ;

    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(!S1[node].U) {

        total1++;

        S1[node].U=total1;

    }

    if(!S1[node].D) {

        total1++;

        S1[node].D=total1;

    }

    up1(S1[node].U,bas,orta,P,Q,K);
    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 376 KB Output is correct
2 Correct 4 ms 488 KB Output is correct
3 Correct 4 ms 564 KB Output is correct
4 Correct 3 ms 644 KB Output is correct
5 Correct 2 ms 644 KB Output is correct
6 Correct 4 ms 656 KB Output is correct
7 Correct 2 ms 656 KB Output is correct
8 Correct 2 ms 656 KB Output is correct
9 Correct 3 ms 656 KB Output is correct
10 Correct 3 ms 656 KB Output is correct
11 Correct 3 ms 656 KB Output is correct
12 Correct 3 ms 656 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 2 ms 656 KB Output is correct
3 Correct 2 ms 656 KB Output is correct
4 Correct 1035 ms 13580 KB Output is correct
5 Correct 541 ms 17956 KB Output is correct
6 Correct 719 ms 19708 KB Output is correct
7 Correct 966 ms 24128 KB Output is correct
8 Correct 591 ms 25984 KB Output is correct
9 Correct 1010 ms 32564 KB Output is correct
10 Correct 799 ms 32564 KB Output is correct
11 Correct 2 ms 32564 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 32564 KB Output is correct
2 Correct 3 ms 32564 KB Output is correct
3 Correct 4 ms 32564 KB Output is correct
4 Correct 2 ms 32564 KB Output is correct
5 Correct 2 ms 32564 KB Output is correct
6 Correct 3 ms 32564 KB Output is correct
7 Correct 2 ms 32564 KB Output is correct
8 Correct 2 ms 32564 KB Output is correct
9 Correct 3 ms 32564 KB Output is correct
10 Correct 3 ms 32564 KB Output is correct
11 Correct 3 ms 32564 KB Output is correct
12 Correct 1441 ms 37528 KB Output is correct
13 Correct 2677 ms 37528 KB Output is correct
14 Correct 422 ms 37528 KB Output is correct
15 Correct 3010 ms 43040 KB Output is correct
16 Correct 338 ms 55200 KB Output is correct
17 Correct 1836 ms 55200 KB Output is correct
18 Correct 2152 ms 65720 KB Output is correct
19 Correct 1938 ms 71216 KB Output is correct
20 Correct 1720 ms 75884 KB Output is correct
21 Correct 2 ms 75884 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 75884 KB Output is correct
2 Correct 3 ms 75884 KB Output is correct
3 Correct 3 ms 75884 KB Output is correct
4 Correct 2 ms 75884 KB Output is correct
5 Correct 2 ms 75884 KB Output is correct
6 Correct 3 ms 75884 KB Output is correct
7 Correct 2 ms 75884 KB Output is correct
8 Correct 3 ms 75884 KB Output is correct
9 Correct 3 ms 75884 KB Output is correct
10 Correct 3 ms 75884 KB Output is correct
11 Correct 3 ms 75884 KB Output is correct
12 Correct 712 ms 75884 KB Output is correct
13 Correct 526 ms 75884 KB Output is correct
14 Correct 973 ms 75884 KB Output is correct
15 Correct 1087 ms 75884 KB Output is correct
16 Correct 649 ms 75884 KB Output is correct
17 Correct 894 ms 75884 KB Output is correct
18 Correct 805 ms 75884 KB Output is correct
19 Correct 1394 ms 75884 KB Output is correct
20 Correct 2484 ms 75884 KB Output is correct
21 Correct 583 ms 75884 KB Output is correct
22 Correct 2970 ms 80820 KB Output is correct
23 Correct 296 ms 93192 KB Output is correct
24 Correct 1834 ms 93192 KB Output is correct
25 Correct 2773 ms 103700 KB Output is correct
26 Correct 2344 ms 109376 KB Output is correct
27 Correct 2289 ms 111540 KB Output is correct
28 Runtime error 3830 ms 257024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Runtime error 2 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 -