Submission #24131

#	Time	Username	Problem	Language	Result	Execution time	Memory
24131		RezwanArefin01	Game (IOI13_game)	C++14	63 / 100	3573 ms	133236 KiB

game

#include "game.h"
#include <bits/stdc++.h>
using namespace std;
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;
}
long long n, m;
vector< vector<long long> > tree;
 
void updateY(int ndx, int lx, int rx, int ndy, int ly, int ry, int y, long long val) {
    if(ly == ry) {
        if(lx == rx) tree[ndx][ndy] = val;
        else tree[ndx][ndy] = gcd(tree[ndx*2][ndy], tree[ndx*2+1][ndy]);
        return;
    } int mid = ly + ry >> 1;
    if(y <= mid) updateY(ndx, lx, rx, ndy*2, ly, mid, y, val);
    else updateY(ndx, lx, rx, ndy*2+1, mid+1, ry, y, val); 
    tree[ndx][ndy] = gcd(tree[ndx][ndy*2], tree[ndx][ndy*2+1]);
}
void updateX(int ndx, int lx, int rx, int x, int y, long long val) {
    if(lx != rx) {
        int mid = lx + rx >> 1;
        if(x <= mid) updateX(ndx*2, lx, mid, x, y, val);
        else updateX(ndx*2+1, mid+1, rx, x,y, val);
    } updateY(ndx, lx, rx, 1, 0, m-1, y,val);
}
  
long long queryY(int ndx, int ndy, int ly, int ry, int y1, int y2) {
    if(ry < y1 || ly > y2) return 0;
    if(y1 <= ly && ry <= y2)  
        return tree[ndx][ndy];
    int mid = ly + ry >> 1;
    return gcd(queryY(ndx, ndy*2, ly, mid, y1, y2), 
           queryY(ndx, ndy*2+1, mid+1, ry, y1, y2));
}
long long queryX(int ndx, int lx, int rx, int x1, int y1, int x2, int y2) {
    if(rx < x1 || lx > x2) return 0;
    if(x1 <= lx && rx <= x2) {
        return queryY(ndx, 1, 0, m-1, y1, y2);
    } int mid = lx + rx >> 1;
    return gcd(queryX(ndx*2, lx, mid, x1,y1,x2,y2),
           queryX(ndx*2+1, mid+1, rx, x1,y1,x2,y2));
}
     
void init(int R, int C) {
    n = R, m = C;
    if(n <= 2000 && m <= 2000) {
        tree.resize(4095);
        for(int i=0; i<4095; i++) 
                tree[i].assign(4095, 0);
    } else {
        tree.resize(26);
        for(int i=0; i<26; i++) 
            tree[i].assign(272141, 0);
    }
}
     
void update(int P, int Q, long long K) { 
    updateX(1, 0, n-1, P, Q, K);
}
     
long long calculate(int P, int Q, int U, int V) {
    return queryX(1, 0, n-1, P,Q,U,V);
}

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;
      ^
game.cpp: In function 'void updateY(int, int, int, int, int, int, int, long long int)':
game.cpp:21:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     } int mid = ly + ry >> 1;
                    ^
game.cpp: In function 'void updateX(int, int, int, int, int, long long int)':
game.cpp:28:22: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
         int mid = lx + rx >> 1;
                      ^
game.cpp: In function 'long long int queryY(int, int, int, int, int, int)':
game.cpp:38:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid = ly + ry >> 1;
                  ^
game.cpp: In function 'long long int queryX(int, int, int, int, int, int, int)':
game.cpp:46:20: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     } int mid = lx + rx >> 1;
                    ^

• Subtask 1: 10 / 10
• Subtask 2: 27 / 27
• Subtask 3: 26 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20