oj.uz

Submission #42766

# Submission time Handle Problem Language Result Execution time Memory
42766 2018-03-03T22:25:46 Z yusufake Game (IOI13_game) C++
63 / 100
 3120 ms 256000 KB 
#include<bits/stdc++.h>
#include "game.h"
 
using namespace std;
 
#define _   int v, int tl, int tr
#define tm  (tl+tr >> 1)
#define sol L[v],tl,tm
#define sag R[v],tm+1,tr
 
#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 * 300;
 
int Y[N],L[N],R[N],posx,posy,lx,ly,rx,ry,id=1;
ll s[N],tt;
 
ll qry_y(_) { 
	if(ly > tr || ry < tl || !v) return 0;
	if (ly <= tl && tr <= ry) return s[v];
	return __gcd(qry_y(sol) , qry_y(sag));
}
ll qry_x(_) { 
	if(lx > tr || rx < tl) return 0;
	if (lx <= tl && tr <= rx) return qry_y(Y[v], 0, mod);
	return __gcd(qry_x(sol) , qry_x(sag));
}
 
void up_y(_, int r1, int r2, bool h){  // s[0] should contain ineffective element
	if(tl == tr){
     if(tl != posy) return;
			if(h) s[v] = tt;
			else s[v] = __gcd(s[r1] , s[r2]);
     return;
	}
	if(posy > tm) { if(!R[v]) R[v] = ++id; up_y(sag,R[r1],R[r2],h); }
	else          { if(!L[v]) L[v] = ++id; up_y(sol,L[r1],L[r2],h); }
	s[v] = __gcd(s[ L[v] ] , s[ R[v] ]);
}
void up_x(_){
	if(tl < tr){
		if(posx > tm) { if(!R[v]) R[v] = ++id; up_x(sag); }
		else          { if(!L[v]) L[v] = ++id; up_x(sol); }
	}
	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

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:8:21: note: in expansion of macro 'tm'
 #define sol L[v],tl,tm
                     ^
game.cpp:28:21: note: in expansion of macro 'sol'
  return __gcd(qry_y(sol) , qry_y(sag));
                     ^
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:9:18: note: in expansion of macro 'tm'
 #define sag R[v],tm+1,tr
                  ^
game.cpp:28:34: note: in expansion of macro 'sag'
  return __gcd(qry_y(sol) , qry_y(sag));
                                  ^
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:8:21: note: in expansion of macro 'tm'
 #define sol L[v],tl,tm
                     ^
game.cpp:33:21: note: in expansion of macro 'sol'
  return __gcd(qry_x(sol) , qry_x(sag));
                     ^
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:9:18: note: in expansion of macro 'tm'
 #define sag R[v],tm+1,tr
                  ^
game.cpp:33:34: note: in expansion of macro 'sag'
  return __gcd(qry_x(sol) , qry_x(sag));
                                  ^
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:43:12: note: in expansion of macro 'tm'
  if(posy > tm) { if(!R[v]) R[v] = ++id; up_y(sag,R[r1],R[r2],h); }
            ^
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:9:18: note: in expansion of macro 'tm'
 #define sag R[v],tm+1,tr
                  ^
game.cpp:43:46: note: in expansion of macro 'sag'
  if(posy > tm) { if(!R[v]) R[v] = ++id; up_y(sag,R[r1],R[r2],h); }
                                              ^
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:8:21: note: in expansion of macro 'tm'
 #define sol L[v],tl,tm
                     ^
game.cpp:44:46: note: in expansion of macro 'sol'
  else          { if(!L[v]) L[v] = ++id; up_y(sol,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:49:13: note: in expansion of macro 'tm'
   if(posx > tm) { if(!R[v]) R[v] = ++id; up_x(sag); }
             ^
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:9:18: note: in expansion of macro 'tm'
 #define sag R[v],tm+1,tr
                  ^
game.cpp:49:47: note: in expansion of macro 'sag'
   if(posx > tm) { if(!R[v]) R[v] = ++id; up_x(sag); }
                                               ^
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:8:21: note: in expansion of macro 'tm'
 #define sol L[v],tl,tm
                     ^
game.cpp:50:47: note: in expansion of macro 'sol'
   else          { if(!L[v]) L[v] = ++id; up_x(sol); }
                                               ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 608 KB Output is correct
3 Correct 4 ms 744 KB Output is correct
4 Correct 1 ms 744 KB Output is correct
5 Correct 1 ms 744 KB Output is correct
6 Correct 4 ms 788 KB Output is correct
7 Correct 1 ms 788 KB Output is correct
8 Correct 1 ms 788 KB Output is correct
9 Correct 3 ms 788 KB Output is correct
10 Correct 2 ms 788 KB Output is correct
11 Correct 2 ms 788 KB Output is correct
12 Correct 2 ms 788 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 788 KB Output is correct
2 Correct 2 ms 788 KB Output is correct
3 Correct 1 ms 788 KB Output is correct
4 Correct 1108 ms 30284 KB Output is correct
5 Correct 883 ms 34600 KB Output is correct
6 Correct 1182 ms 36228 KB Output is correct
7 Correct 1291 ms 40640 KB Output is correct
8 Correct 790 ms 40640 KB Output is correct
9 Correct 1314 ms 49868 KB Output is correct
10 Correct 1136 ms 53956 KB Output is correct
11 Correct 2 ms 53956 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 53956 KB Output is correct
2 Correct 4 ms 53956 KB Output is correct
3 Correct 4 ms 53956 KB Output is correct
4 Correct 1 ms 53956 KB Output is correct
5 Correct 2 ms 53956 KB Output is correct
6 Correct 3 ms 53956 KB Output is correct
7 Correct 1 ms 53956 KB Output is correct
8 Correct 2 ms 53956 KB Output is correct
9 Correct 3 ms 53956 KB Output is correct
10 Correct 2 ms 53956 KB Output is correct
11 Correct 2 ms 53956 KB Output is correct
12 Correct 1656 ms 53956 KB Output is correct
13 Correct 2674 ms 53956 KB Output is correct
14 Correct 641 ms 53956 KB Output is correct
15 Correct 3120 ms 53956 KB Output is correct
16 Correct 698 ms 53956 KB Output is correct
17 Correct 1698 ms 53956 KB Output is correct
18 Correct 2651 ms 58660 KB Output is correct
19 Correct 2403 ms 64052 KB Output is correct
20 Correct 2226 ms 69048 KB Output is correct
21 Correct 2 ms 69048 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 69048 KB Output is correct
2 Correct 4 ms 69048 KB Output is correct
3 Correct 4 ms 69048 KB Output is correct
4 Correct 2 ms 69048 KB Output is correct
5 Correct 2 ms 69048 KB Output is correct
6 Correct 3 ms 69048 KB Output is correct
7 Correct 2 ms 69048 KB Output is correct
8 Correct 2 ms 69048 KB Output is correct
9 Correct 3 ms 69048 KB Output is correct
10 Correct 2 ms 69048 KB Output is correct
11 Correct 2 ms 69048 KB Output is correct
12 Correct 1129 ms 84648 KB Output is correct
13 Correct 840 ms 88820 KB Output is correct
14 Correct 1232 ms 90580 KB Output is correct
15 Correct 1288 ms 94728 KB Output is correct
16 Correct 802 ms 94728 KB Output is correct
17 Correct 1257 ms 103884 KB Output is correct
18 Correct 1176 ms 108100 KB Output is correct
19 Correct 1653 ms 108100 KB Output is correct
20 Correct 2633 ms 108100 KB Output is correct
21 Correct 658 ms 108100 KB Output is correct
22 Correct 3036 ms 110212 KB Output is correct
23 Correct 737 ms 119968 KB Output is correct
24 Correct 1584 ms 121212 KB Output is correct
25 Correct 2487 ms 130472 KB Output is correct
26 Correct 2242 ms 136032 KB Output is correct
27 Correct 2073 ms 140724 KB Output is correct
28 Runtime error 1060 ms 256000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256000 KB Output is correct
2 Correct 3 ms 256000 KB Output is correct
3 Correct 4 ms 256000 KB Output is correct
4 Correct 1 ms 256000 KB Output is correct
5 Correct 1 ms 256000 KB Output is correct
6 Correct 3 ms 256000 KB Output is correct
7 Correct 1 ms 256000 KB Output is correct
8 Correct 1 ms 256000 KB Output is correct
9 Correct 3 ms 256000 KB Output is correct
10 Correct 2 ms 256000 KB Output is correct
11 Correct 2 ms 256000 KB Output is correct
12 Correct 1077 ms 256000 KB Output is correct
13 Correct 809 ms 256000 KB Output is correct
14 Correct 1223 ms 256000 KB Output is correct
15 Correct 1286 ms 256000 KB Output is correct
16 Correct 778 ms 256000 KB Output is correct
17 Correct 1257 ms 256000 KB Output is correct
18 Correct 1226 ms 256000 KB Output is correct
19 Correct 1622 ms 256000 KB Output is correct
20 Correct 2608 ms 256000 KB Output is correct
21 Correct 677 ms 256000 KB Output is correct
22 Correct 3102 ms 256000 KB Output is correct
23 Correct 737 ms 256000 KB Output is correct
24 Correct 1617 ms 256000 KB Output is correct
25 Correct 2718 ms 256000 KB Output is correct
26 Correct 2549 ms 256000 KB Output is correct
27 Correct 2095 ms 256000 KB Output is correct
28 Runtime error 1229 ms 256000 KB Execution killed with signal 11 (could be triggered by violating memory limits)
29 Halted 0 ms 0 KB -