oj.uz

Submission #29941

# Submission time Handle Problem Language Result Execution time Memory
29941 2017-07-21T11:10:57 Z osmanorhan Game (IOI13_game) C++14
0 / 100
 0 ms 160780 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 = 10020;
const int maxm = 10000020;

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

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;
}

Lint segment[maxm];
int l[maxm], r[maxm], N = 1; // left and right node's index for each node in small segment_trees
int tl[maxn*32], tr[maxn*32]; // left and right node's index for each node in big segment_tree
int x, y, row, c;
int x1, x2, y1, y2;
Lint val;

int up2( int n, int b, int s, int tp ) {
    if( b > y || s < y ) return n;

    if( n == 0 ) n = ++N;
    if( y <= b && s <= y ) {
        if( tp ) segment[n] = val;
        else segment[n] = gcd2( segment[n], val );
        return n;
    }
    l[n] = up2( l[n], b, ort, tp );
    r[n] = up2( r[n], ort+1, s, tp );
    segment[n] = gcd2( segment[l[n]], segment[r[n]] );
    return n;
}

int up( int n, int b, int s ) {
    if( b > x || s < x ) return n;

    if( n == 0 ) n = ++N;
    if( x <= b && s <= x ) {
        up2( n, 0, c-1, 1 );
        return n;
    }
    up2( n, 0, c-1, 0 );
    tl[n] = up( tl[n], b, ort );
    tr[n] = up( tr[n], ort+1, s );
    return n;
}

Lint get2( int n, int b, int s ) {
    if( !n || b > y2 || s < y1 ) return 0;
    if( y1 <= b && s <= y2 ) return segment[n];
    return gcd2( get2( l[n], b, ort ), get2( r[n], ort+1, s ) );
}

Lint get( int n, int b, int s ) {
    if( !n || b > x2 || s < x1 ) return 0;
    if( x1 <= b && s <= x2 ) return get2( n, 0, c-1 );
    return gcd2( get( tl[n], b, ort ), get( tr[n], ort+1, s ) );
}

void init(int R, int C) {
    row = R;
    c = C;
}

void update(int P, int Q, long long K) {
    x = P;
    y = Q;
    val = K;
    up( 1, 0, row-1 );
}

long long calculate(int P, int Q, int U, int V) {
    x1 = P;
    y1 = Q;
    x2 = U;
    y2 = V;
    return get( 1, 0, row-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
0 / 10.0

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

Subtask #2
0 / 27.0

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

Subtask #3
0 / 26.0

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

Subtask #4
0 / 17.0

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

Subtask #5
0 / 20.0

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