oj.uz

Submission #56844

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

#define ll long long
#define MAXQ 22005
#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 2 ms 248 KB Output is correct
2 Correct 4 ms 484 KB Output is correct
3 Correct 4 ms 648 KB Output is correct
4 Correct 3 ms 648 KB Output is correct
5 Correct 3 ms 648 KB Output is correct
6 Correct 3 ms 648 KB Output is correct
7 Correct 4 ms 648 KB Output is correct
8 Correct 2 ms 648 KB Output is correct
9 Correct 3 ms 648 KB Output is correct
10 Correct 3 ms 648 KB Output is correct
11 Correct 3 ms 648 KB Output is correct
12 Correct 3 ms 648 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 648 KB Output is correct
2 Correct 2 ms 660 KB Output is correct
3 Correct 3 ms 660 KB Output is correct
4 Correct 936 ms 13648 KB Output is correct
5 Correct 591 ms 17928 KB Output is correct
6 Correct 751 ms 19552 KB Output is correct
7 Correct 942 ms 23880 KB Output is correct
8 Correct 637 ms 26036 KB Output is correct
9 Correct 824 ms 32488 KB Output is correct
10 Correct 859 ms 32488 KB Output is correct
11 Correct 3 ms 32488 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 32488 KB Output is correct
2 Correct 3 ms 32488 KB Output is correct
3 Correct 3 ms 32488 KB Output is correct
4 Correct 2 ms 32488 KB Output is correct
5 Correct 3 ms 32488 KB Output is correct
6 Correct 3 ms 32488 KB Output is correct
7 Correct 2 ms 32488 KB Output is correct
8 Correct 2 ms 32488 KB Output is correct
9 Correct 4 ms 32488 KB Output is correct
10 Correct 3 ms 32488 KB Output is correct
11 Correct 3 ms 32488 KB Output is correct
12 Correct 1351 ms 37444 KB Output is correct
13 Correct 2557 ms 37444 KB Output is correct
14 Correct 462 ms 37444 KB Output is correct
15 Correct 3157 ms 42816 KB Output is correct
16 Correct 381 ms 55244 KB Output is correct
17 Correct 1709 ms 55244 KB Output is correct
18 Correct 2471 ms 65768 KB Output is correct
19 Correct 2294 ms 71464 KB Output is correct
20 Correct 2153 ms 76172 KB Output is correct
21 Correct 2 ms 76172 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 76172 KB Output is correct
2 Correct 3 ms 76172 KB Output is correct
3 Correct 3 ms 76172 KB Output is correct
4 Correct 3 ms 76172 KB Output is correct
5 Correct 2 ms 76172 KB Output is correct
6 Correct 3 ms 76172 KB Output is correct
7 Correct 3 ms 76172 KB Output is correct
8 Correct 3 ms 76172 KB Output is correct
9 Correct 3 ms 76172 KB Output is correct
10 Correct 3 ms 76172 KB Output is correct
11 Correct 3 ms 76172 KB Output is correct
12 Correct 810 ms 76172 KB Output is correct
13 Correct 600 ms 76172 KB Output is correct
14 Correct 676 ms 76172 KB Output is correct
15 Correct 758 ms 76172 KB Output is correct
16 Correct 546 ms 76172 KB Output is correct
17 Correct 821 ms 76172 KB Output is correct
18 Correct 897 ms 76172 KB Output is correct
19 Correct 1367 ms 76172 KB Output is correct
20 Correct 2641 ms 76172 KB Output is correct
21 Correct 475 ms 76172 KB Output is correct
22 Correct 3014 ms 81016 KB Output is correct
23 Correct 324 ms 93544 KB Output is correct
24 Correct 1566 ms 93544 KB Output is correct
25 Correct 2640 ms 104132 KB Output is correct
26 Correct 2320 ms 109624 KB Output is correct
27 Correct 2364 ms 114244 KB Output is correct
28 Runtime error 1465 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.
29 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 -