Submission #122033

#	Time	Username	Problem	Language	Result	Execution time	Memory
122033		yusufake	Game (IOI13_game)	C++98	80 / 100	7320 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)

typedef long long ll;
typedef pair < int , int > pp;
 
const int mod = 1e9 + 7;
const int x_N   = 22000 * 23;
const int y_N   = 22000 * 23 * 23;

int x_to_Y[x_N],x_L[x_N],x_R[x_N],x_id = 1;
int             y_L[y_N],y_R[y_N],y_id;
ll s[y_N]; // segment tree values are stored only for -y axis


// 0 is empty node 
// s[0] should be ineffective element
// x_to_Y[0], L[0], and R[0] should be 0
// 1 is the root of the -x axis segment tree
// x_to_Y[v] is the root of the segment tree of the interval that corresponds to node 'v' in -x axis segment tree
 
ll gcd(ll u, ll v) {
    ll r;
    while (v != 0) { r = u % v; u = v; v = r; }
    return u;
} 
 
ll qry_y(_, int ly, int ry) { 
	if(ly > tr || ry < tl || !v) return 0;
	if (ly <= tl && tr <= ry) return s[v];
	return gcd(qry_y(y_L[v],tl,tm,ly,ry) , qry_y(y_R[v],tm+1,tr,ly,ry));
}
ll qry_x(_, int lx, int rx, int ly, int ry) { 
	if(lx > tr || rx < tl) return 0;
	if (lx <= tl && tr <= rx) return qry_y(x_to_Y[v], 0, mod, ly, ry);
	return gcd(qry_x(x_L[v],tl,tm,lx,rx,ly,ry) , qry_x(x_R[v],tm+1,tr,lx,rx,ly,ry));
}
 
void up_y(_, int posy, int r1, int r2, ll t){  
    if(tl == tr){
		s[v] = t == -1 ? gcd(s[r1] , s[r2]) : t;
		return;
	}
	if(posy > tm) { if(!y_R[v]) y_R[v] = ++y_id; up_y(y_R[v],tm+1,tr,posy,y_R[r1],y_R[r2],t); }
	else          { if(!y_L[v]) y_L[v] = ++y_id; up_y(y_L[v],tl,tm,  posy,y_L[r1],y_L[r2],t); }
	s[v] = gcd(s[ y_L[v] ] , s[ y_R[v] ]);
}
void up_x(_, int posx, int posy, ll t){
	if(tl < tr){
		if(posx > tm) { if(!x_R[v]) x_R[v] = ++x_id; up_x(x_R[v],tm+1,tr,posx,posy,t); }
		else          { if(!x_L[v]) x_L[v] = ++x_id; up_x(x_L[v],tl,tm,  posx,posy,t); }
	}
	if(!x_to_Y[v]) x_to_Y[v] = ++y_id;
	up_y(x_to_Y[v],0,mod,posy,x_to_Y[ x_L[v] ],x_to_Y[ x_R[v] ],(tl==tr?t:-1));
}
 
 
void update(int posx, int posy, ll t){
	up_x(1,0,mod,posx,posy,t);
}	

ll calculate(int lx, int ly, int rx, int ry){
	return qry_x(1,0,mod,lx,rx,ly,ry);
}	
 
void init(int a, int b) {
    memset(s , 0 , sizeof s);
    memset(x_L , 0 , sizeof x_L);
    memset(x_R , 0 , sizeof x_R);
    memset(y_L , 0 , sizeof y_L);
    memset(y_R , 0 , sizeof y_R);
    memset(x_to_Y , 0 , sizeof x_to_Y);
}

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, int, int)':
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm (tl + tr >> 1)
             ~~~^~~
game.cpp:36:29: note: in expansion of macro 'tm'
  return gcd(qry_y(y_L[v],tl,tm,ly,ry) , qry_y(y_R[v],tm+1,tr,ly,ry));
                             ^~
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm (tl + tr >> 1)
             ~~~^~~
game.cpp:36:54: note: in expansion of macro 'tm'
  return gcd(qry_y(y_L[v],tl,tm,ly,ry) , qry_y(y_R[v],tm+1,tr,ly,ry));
                                                      ^~
game.cpp: In function 'll qry_x(int, int, int, int, int, int, int)':
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm (tl + tr >> 1)
             ~~~^~~
game.cpp:41:29: note: in expansion of macro 'tm'
  return gcd(qry_x(x_L[v],tl,tm,lx,rx,ly,ry) , qry_x(x_R[v],tm+1,tr,lx,rx,ly,ry));
                             ^~
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm (tl + tr >> 1)
             ~~~^~~
game.cpp:41:60: note: in expansion of macro 'tm'
  return gcd(qry_x(x_L[v],tl,tm,lx,rx,ly,ry) , qry_x(x_R[v],tm+1,tr,lx,rx,ly,ry));
                                                            ^~
game.cpp: In function 'void up_y(int, int, int, int, int, int, ll)':
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(!y_R[v]) y_R[v] = ++y_id; up_y(y_R[v],tm+1,tr,posy,y_R[r1],y_R[r2],t); }
            ^~
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm (tl + tr >> 1)
             ~~~^~~
game.cpp:49:59: note: in expansion of macro 'tm'
  if(posy > tm) { if(!y_R[v]) y_R[v] = ++y_id; up_y(y_R[v],tm+1,tr,posy,y_R[r1],y_R[r2],t); }
                                                           ^~
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm (tl + tr >> 1)
             ~~~^~~
game.cpp:50:62: note: in expansion of macro 'tm'
  else          { if(!y_L[v]) y_L[v] = ++y_id; up_y(y_L[v],tl,tm,  posy,y_L[r1],y_L[r2],t); }
                                                              ^~
game.cpp: In function 'void up_x(int, int, int, int, int, ll)':
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(!x_R[v]) x_R[v] = ++x_id; up_x(x_R[v],tm+1,tr,posx,posy,t); }
             ^~
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm (tl + tr >> 1)
             ~~~^~~
game.cpp:55:60: note: in expansion of macro 'tm'
   if(posx > tm) { if(!x_R[v]) x_R[v] = ++x_id; up_x(x_R[v],tm+1,tr,posx,posy,t); }
                                                            ^~
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm (tl + tr >> 1)
             ~~~^~~
game.cpp:56:63: note: in expansion of macro 'tm'
   else          { if(!x_L[v]) x_L[v] = ++x_id; up_x(x_L[v],tl,tm,  posx,posy,t); }
                                                               ^~

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