Submission #42771

#	Time	Username	Problem	Language	Result	Execution time	Memory
42771		yusufake	Game (IOI13_game)	C++98	80 / 100	12540 ms	256000 KiB

game

#include<bits/stdc++.h>
#include "game.h"
 
using namespace std;
 
#define _   int v, int tl, int tr
#define tm  (tl+tr >> 1)
 
#define mp make_pair
#define pb push_back
#define st first
#define nd second
 
typedef long long ll;
typedef pair < int , int > pp;
 
const int mod = 1e9 + 7;
const int N   = 22000 * 525;
 
int Y[N],L[N],R[N],posx,posy,lx,ly,rx,ry,id=1;
ll s[N],tt;
 
ll gcd(ll u, ll v) {
    ll r;
    while ( v != 0) {
        r = u % v;
        u = v;
        v = r;
    }
    return u;
}

ll qry_y(int v, int tl, int tr) { 
	if(ly > tr || ry < tl || !v) return 0;
	if (ly <= tl && tr <= ry) return s[v];
	return gcd(qry_y(L[v],tl,tm) , qry_y(R[v],tm+1,tr));
}
ll qry_x(int v, int tl, int tr) { 
	if(lx > tr || rx < tl) return 0;
	if (lx <= tl && tr <= rx) return qry_y(Y[v], 0, mod);
	return gcd(qry_x(L[v],tl,tm) , qry_x(R[v],tm+1,tr));
}
 
void up_y(int v, int tl, int tr, int r1, int r2, bool h){ 
	if(tl == tr){
		s[v] = h ? tt : gcd(s[r1] , s[r2]);
		return;
	}
	if(posy > tm) { if(!R[v]) R[v] = ++id; up_y(R[v],tm+1,tr,R[r1],R[r2],h); }
	else          { if(!L[v]) L[v] = ++id; up_y(L[v],tl,tm,L[r1],L[r2],h); }
	s[v] = gcd(s[ L[v] ] , s[ R[v] ]);
}
void up_x(int v, int tl, int tr){
	if(tl < tr){
		if(posx > tm) { if(!R[v]) R[v] = ++id; up_x(R[v],tm+1,tr); }
		else          { if(!L[v]) L[v] = ++id; up_x(L[v],tl,tm); }
	}
	if(!Y[v]) Y[v] = ++id;
	up_y(Y[v],0,mod,Y[ L[v] ],Y[ R[v] ],(tl==tr));
}
 
void update(int x, int y, ll t){
	posx = x;
	posy = y;
	tt = t;
	up_x(1,0,mod);
}	
ll calculate(int a, int b, int a2, int b2){
	lx = a; ly = b;
	rx = a2; ry = b2;
	return qry_x(1,0,mod);
}	
 
void init(int a, int b) {}

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 'll qry_y(int, int, int)':
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:36:27: note: in expansion of macro 'tm'
  return gcd(qry_y(L[v],tl,tm) , qry_y(R[v],tm+1,tr));
                           ^
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:36:44: note: in expansion of macro 'tm'
  return gcd(qry_y(L[v],tl,tm) , qry_y(R[v],tm+1,tr));
                                            ^
game.cpp: In function 'll qry_x(int, int, int)':
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:41:27: note: in expansion of macro 'tm'
  return gcd(qry_x(L[v],tl,tm) , qry_x(R[v],tm+1,tr));
                           ^
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:41:44: note: in expansion of macro 'tm'
  return gcd(qry_x(L[v],tl,tm) , qry_x(R[v],tm+1,tr));
                                            ^
game.cpp: In function 'void up_y(int, int, int, int, int, bool)':
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:49:12: note: in expansion of macro 'tm'
  if(posy > tm) { if(!R[v]) R[v] = ++id; up_y(R[v],tm+1,tr,R[r1],R[r2],h); }
            ^
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:49:51: note: in expansion of macro 'tm'
  if(posy > tm) { if(!R[v]) R[v] = ++id; up_y(R[v],tm+1,tr,R[r1],R[r2],h); }
                                                   ^
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:50:54: note: in expansion of macro 'tm'
  else          { if(!L[v]) L[v] = ++id; up_y(L[v],tl,tm,L[r1],L[r2],h); }
                                                      ^
game.cpp: In function 'void up_x(int, int, int)':
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:55:13: note: in expansion of macro 'tm'
   if(posx > tm) { if(!R[v]) R[v] = ++id; up_x(R[v],tm+1,tr); }
             ^
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:55:52: note: in expansion of macro 'tm'
   if(posx > tm) { if(!R[v]) R[v] = ++id; up_x(R[v],tm+1,tr); }
                                                    ^
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:56:55: note: in expansion of macro 'tm'
   else          { if(!L[v]) L[v] = ++id; up_x(L[v],tl,tm); }
                                                       ^

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