Submission #29930

#	Time	Username	Problem	Language	Result	Execution time	Memory
29930		osmanorhan	Game (IOI13_game)	C++14	0 / 100	0 ms	160780 KiB

game

#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 ) {
    if( b > y || s < y ) return n;

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

int up( int n, int b, int s ) {
    //printf("%d --> %d %d (up=%d %d -- %lld)\n",n,b,s,x,y,val);
    if( b > x || s < x ) return n;

    if( n == 0 ) n = ++N;
    //printf("passed %d --> %d %d (up=%d %d -- %lld)\n",n,b,s,x,y,val);
    if( x <= b && s <= x ) {
        up2( n, 0, c-1 );
        return n;
    }
    up2( n, 0, c-1 );
    tl[n] = up( tl[n], b, ort );
    tr[n] = up( tr[n], ort+1, s );
    //segment[n] = gcd( segment[tl[n]], segment[tr[n]] );
    return n;
}

Lint get2( int n, int b, int s ) {
    //printf("asd2 %d --> %d %d\n",n,b,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 ) {
    //printf("asd %d --> %d %d\n",n,b,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) {
    //for(int i=1;i<=N;i++)
        //printf("asd tl,tr = %d %d -- l,r = %d %d\n",tl[i],tr[i],l[i],r[i]);
    x1 = P;
    y1 = Q;
    x2 = U;
    y2 = V;
    return get( 1, 0, row-1 );
}

Compilation message (stderr)

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
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20