oj.uz

Submission #30031

# Submission time Handle Problem Language Result Execution time Memory
30031 2017-07-21T15:02:49 Z osmanorhan Game (IOI13_game) C++14
36 / 100
 3163 ms 133368 KB 
#include "game.h"
#include <bits/stdc++.h>
#define all( x ) x.begin(), x.end()
#define ort (b+s)/2
#define fi first
#define se second
#define pb push_back
#define y1 asdaswe
#define y2 asdaswasdf

using namespace std;

const int maxn = 4100;
const int maxm = 15000020;

typedef long long Lint;
typedef pair<int,int> ii;

long long gcd(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

Lint segment[maxn][maxn];
int x1, x2, y2, y1, ar[maxn], n;
Lint val;

void up2( int k, int b, int s, int tp, bool var ) {
    if( b > y2 || s < x2 ) return;
    if( x2 <= b && s <= y2 ) {
        if( var ) segment[k][tp] = val;
        else
            segment[k][tp] = gcd( segment[k][tp+tp], segment[k][tp+tp+1] );
        //printf("-- %d %d %d %d %d -- %lld\n",k,b,s,tp,var,segment[k][tp]);
        //if( tp == 2049 ) printf("HOW %d\n",segment[1][2049]);
        return;
    }
    up2( k+k, b, ort, tp, var );
    up2( k+k+1, ort+1, s, tp, var );
    segment[k][tp] = gcd( segment[k+k][tp], segment[k+k+1][tp] );
}



void up( int k, int b, int s ) {
    //push( k );
    if( b > y1 || s < x1 ) return;
    if( x1 <= b && s <= y1 ) {
        up2( 1, 0, n-1, k, 1 );
        return;
    }
    up( k+k, b, ort );
    up( k+k+1, ort+1, s );
    up2( 1, 0, n-1, k, 0 );
}

Lint find2( int k, int b, int s, int tp ) {
    if( b > y2 || s < x2 ) return 0;
    if( x2 <= b && s <= y2 ) return segment[k][tp];
    return gcd( find2( k+k, b, ort, tp ), find2( k+k+1, ort+1, s, tp ) );
}

Lint find( int k, int b, int s ) {
    //push( k );
    if( b > y1 || s < x1 ) return 0;
    if( x1 <= b && s <= y1 ) return find2( 1, 0, n-1, k );
    return gcd( find( k+k, b, ort ), find( k+k+1, ort+1, s ) );
}

void init(int R, int C) {
    n = 1<<11;
}

void update(int P, int Q, long long K) {
    x1 = y1 = P;
    x2 = y2 = Q;
    val = K;
    up( 1, 0, n-1 );
}

long long calculate(int P, int Q, int U, int V) {
    x1 = P;
    x2 = Q;
    y1 = U;
    y2 = V;
    return find( 1, 0, n-1 );
}

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

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 133368 KB Output is correct
2 Correct 0 ms 133368 KB Output is correct
3 Correct 0 ms 133368 KB Output is correct
4 Incorrect 263 ms 133368 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 133368 KB Output is correct
2 Correct 0 ms 133368 KB Output is correct
3 Correct 3 ms 133368 KB Output is correct
4 Correct 0 ms 133368 KB Output is correct
5 Correct 0 ms 133368 KB Output is correct
6 Correct 0 ms 133368 KB Output is correct
7 Correct 0 ms 133368 KB Output is correct
8 Correct 0 ms 133368 KB Output is correct
9 Correct 3 ms 133368 KB Output is correct
10 Correct 0 ms 133368 KB Output is correct
11 Correct 3 ms 133368 KB Output is correct
12 Correct 1523 ms 133368 KB Output is correct
13 Correct 2753 ms 133368 KB Output is correct
14 Correct 1022 ms 133368 KB Output is correct
15 Correct 3163 ms 133368 KB Output is correct
16 Correct 439 ms 133368 KB Output is correct
17 Correct 2166 ms 133368 KB Output is correct
18 Correct 2836 ms 133368 KB Output is correct
19 Correct 2623 ms 133368 KB Output is correct
20 Correct 1899 ms 133368 KB Output is correct
21 Correct 0 ms 133368 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 133368 KB Output is correct
2 Correct 0 ms 133368 KB Output is correct
3 Correct 3 ms 133368 KB Output is correct
4 Correct 0 ms 133368 KB Output is correct
5 Correct 0 ms 133368 KB Output is correct
6 Correct 3 ms 133368 KB Output is correct
7 Correct 0 ms 133368 KB Output is correct
8 Correct 0 ms 133368 KB Output is correct
9 Correct 0 ms 133368 KB Output is correct
10 Correct 0 ms 133368 KB Output is correct
11 Correct 0 ms 133368 KB Output is correct
12 Incorrect 289 ms 133368 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 133368 KB Output is correct
2 Correct 0 ms 133368 KB Output is correct
3 Correct 0 ms 133368 KB Output is correct
4 Correct 0 ms 133368 KB Output is correct
5 Correct 0 ms 133368 KB Output is correct
6 Correct 0 ms 133368 KB Output is correct
7 Correct 0 ms 133368 KB Output is correct
8 Correct 0 ms 133368 KB Output is correct
9 Correct 0 ms 133368 KB Output is correct
10 Correct 0 ms 133368 KB Output is correct
11 Correct 0 ms 133368 KB Output is correct
12 Incorrect 219 ms 133368 KB Output isn't correct
13 Halted 0 ms 0 KB -