oj.uz

Submission #121967

# Submission time Handle Problem Language Result Execution time Memory
121967 2019-06-27T09:59:46 Z yusufake Game (IOI13_game) C++
80 / 100
 7599 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 * 29 * 29;

int Y[N],L[N],R[N],id;
ll s[N];
 
// 0 is empty node 
// s[0] should be ineffective element
// Y[0], L[0], and R[0] should be 0
// 1 is the root of the -x axis segment tree
// 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(sol,ly,ry) , qry_y(sag,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(Y[v], 0, mod, ly, ry);
	return gcd(qry_x(sol,lx,rx,ly,ry) , qry_x(sag,lx,rx,ly,ry));
}
 
void up_y(_, int posy, int r1, int r2, ll t){  
    if(id == N - 5) while(1);
    if(tl == tr){
		s[v] = t == -1 ? gcd(s[r1] , s[r2]) : t;
		return;
	}
	if(posy > tm) { if(!R[v]) R[v] = ++id; up_y(sag,posy,R[r1],R[r2],t); }
	else          { if(!L[v]) L[v] = ++id; up_y(sol,posy,L[r1],L[r2],t); }
	s[v] = gcd(s[ L[v] ] , s[ R[v] ]);
}
void up_x(_, int posx, int posy, ll t){
    if(id == N - 5) while(1);
	if(tl < tr){
		if(posx > tm) { if(!R[v]) R[v] = ++id; up_x(sag,posx,posy,t); }
		else          { if(!L[v]) L[v] = ++id; up_x(sol,posx,posy,t); }
	}
	if(!Y[v]) Y[v] = ++id;
	up_y(Y[v],0,mod,posy,Y[ L[v] ],Y[ 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(Y , 0 , sizeof Y);
//    memset(L , 0 , sizeof L);
//    memset(R , 0 , sizeof R);
    id = 1;
}

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, 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:40:19: note: in expansion of macro 'sol'
  return gcd(qry_y(sol,ly,ry) , qry_y(sag,ly,ry));
                   ^~~
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:40:38: note: in expansion of macro 'sag'
  return gcd(qry_y(sol,ly,ry) , qry_y(sag,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:8:21: note: in expansion of macro 'tm'
 #define sol L[v],tl,tm
                     ^~
game.cpp:45:19: note: in expansion of macro 'sol'
  return gcd(qry_x(sol,lx,rx,ly,ry) , qry_x(sag,lx,rx,ly,ry));
                   ^~~
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:45:44: note: in expansion of macro 'sag'
  return gcd(qry_x(sol,lx,rx,ly,ry) , qry_x(sag,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:54:12: note: in expansion of macro 'tm'
  if(posy > tm) { if(!R[v]) R[v] = ++id; up_y(sag,posy,R[r1],R[r2],t); }
            ^~
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:54:46: note: in expansion of macro 'sag'
  if(posy > tm) { if(!R[v]) R[v] = ++id; up_y(sag,posy,R[r1],R[r2],t); }
                                              ^~~
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:55:46: note: in expansion of macro 'sol'
  else          { if(!L[v]) L[v] = ++id; up_y(sol,posy,L[r1],L[r2],t); }
                                              ^~~
game.cpp: In function 'void up_x(int, int, int, int, int, ll)':
game.cpp:59:21: warning: this 'while' clause does not guard... [-Wmisleading-indentation]
     if(id == N - 5) while(1);
                     ^~~~~
game.cpp:60:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'while'
  if(tl < tr){
  ^~
game.cpp:7:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
              ~~^~
game.cpp:61:13: note: in expansion of macro 'tm'
   if(posx > tm) { if(!R[v]) R[v] = ++id; up_x(sag,posx,posy,t); }
             ^~
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:61:47: note: in expansion of macro 'sag'
   if(posx > tm) { if(!R[v]) R[v] = ++id; up_x(sag,posx,posy,t); }
                                               ^~~
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:62:47: note: in expansion of macro 'sol'
   else          { if(!L[v]) L[v] = ++id; up_x(sol,posx,posy,t); }
                                               ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 109 ms 145116 KB Output is correct
2 Correct 111 ms 145244 KB Output is correct
3 Correct 111 ms 145400 KB Output is correct
4 Correct 108 ms 145144 KB Output is correct
5 Correct 109 ms 145144 KB Output is correct
6 Correct 110 ms 145272 KB Output is correct
7 Correct 116 ms 145216 KB Output is correct
8 Correct 116 ms 145144 KB Output is correct
9 Correct 117 ms 145272 KB Output is correct
10 Correct 115 ms 145272 KB Output is correct
11 Correct 117 ms 145140 KB Output is correct
12 Correct 117 ms 145144 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 145160 KB Output is correct
2 Correct 109 ms 145144 KB Output is correct
3 Correct 109 ms 145124 KB Output is correct
4 Correct 1207 ms 161420 KB Output is correct
5 Correct 954 ms 161744 KB Output is correct
6 Correct 1424 ms 158636 KB Output is correct
7 Correct 1419 ms 158260 KB Output is correct
8 Correct 943 ms 154404 KB Output is correct
9 Correct 1509 ms 158532 KB Output is correct
10 Correct 1561 ms 158048 KB Output is correct
11 Correct 117 ms 145152 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 117 ms 145172 KB Output is correct
2 Correct 115 ms 145312 KB Output is correct
3 Correct 112 ms 145272 KB Output is correct
4 Correct 116 ms 145144 KB Output is correct
5 Correct 113 ms 145144 KB Output is correct
6 Correct 113 ms 145272 KB Output is correct
7 Correct 109 ms 145172 KB Output is correct
8 Correct 112 ms 145144 KB Output is correct
9 Correct 119 ms 145304 KB Output is correct
10 Correct 117 ms 145168 KB Output is correct
11 Correct 114 ms 145144 KB Output is correct
12 Correct 1881 ms 154488 KB Output is correct
13 Correct 2676 ms 149664 KB Output is correct
14 Correct 749 ms 146780 KB Output is correct
15 Correct 3146 ms 151432 KB Output is correct
16 Correct 815 ms 154680 KB Output is correct
17 Correct 1998 ms 152732 KB Output is correct
18 Correct 3123 ms 154916 KB Output is correct
19 Correct 2784 ms 155064 KB Output is correct
20 Correct 2540 ms 154548 KB Output is correct
21 Correct 108 ms 145144 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 145144 KB Output is correct
2 Correct 119 ms 145396 KB Output is correct
3 Correct 114 ms 145268 KB Output is correct
4 Correct 111 ms 145164 KB Output is correct
5 Correct 109 ms 145200 KB Output is correct
6 Correct 111 ms 145336 KB Output is correct
7 Correct 113 ms 145272 KB Output is correct
8 Correct 109 ms 145144 KB Output is correct
9 Correct 109 ms 145228 KB Output is correct
10 Correct 111 ms 145272 KB Output is correct
11 Correct 108 ms 145220 KB Output is correct
12 Correct 1212 ms 161436 KB Output is correct
13 Correct 930 ms 161708 KB Output is correct
14 Correct 1366 ms 158544 KB Output is correct
15 Correct 1475 ms 158432 KB Output is correct
16 Correct 916 ms 154268 KB Output is correct
17 Correct 1417 ms 158464 KB Output is correct
18 Correct 1309 ms 158040 KB Output is correct
19 Correct 1822 ms 154492 KB Output is correct
20 Correct 2575 ms 149652 KB Output is correct
21 Correct 726 ms 146608 KB Output is correct
22 Correct 2969 ms 151448 KB Output is correct
23 Correct 797 ms 154576 KB Output is correct
24 Correct 1980 ms 152980 KB Output is correct
25 Correct 3306 ms 156096 KB Output is correct
26 Correct 2700 ms 156156 KB Output is correct
27 Correct 2614 ms 155592 KB Output is correct
28 Correct 1292 ms 241172 KB Output is correct
29 Correct 2869 ms 253344 KB Output is correct
30 Correct 7538 ms 215192 KB Output is correct
31 Correct 6788 ms 198920 KB Output is correct
32 Correct 787 ms 147036 KB Output is correct
33 Correct 1025 ms 147872 KB Output is correct
34 Correct 1605 ms 250192 KB Output is correct
35 Correct 2396 ms 199252 KB Output is correct
36 Correct 4432 ms 250552 KB Output is correct
37 Correct 3819 ms 250464 KB Output is correct
38 Correct 3657 ms 250120 KB Output is correct
39 Correct 2867 ms 226508 KB Output is correct
40 Correct 117 ms 145144 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 145144 KB Output is correct
2 Correct 118 ms 145224 KB Output is correct
3 Correct 117 ms 145268 KB Output is correct
4 Correct 115 ms 145144 KB Output is correct
5 Correct 114 ms 145272 KB Output is correct
6 Correct 114 ms 145332 KB Output is correct
7 Correct 112 ms 145308 KB Output is correct
8 Correct 121 ms 145288 KB Output is correct
9 Correct 112 ms 145244 KB Output is correct
10 Correct 117 ms 145284 KB Output is correct
11 Correct 109 ms 145272 KB Output is correct
12 Correct 1196 ms 162196 KB Output is correct
13 Correct 967 ms 162252 KB Output is correct
14 Correct 1446 ms 159352 KB Output is correct
15 Correct 1519 ms 159040 KB Output is correct
16 Correct 862 ms 154720 KB Output is correct
17 Correct 1363 ms 159056 KB Output is correct
18 Correct 1251 ms 158684 KB Output is correct
19 Correct 1753 ms 155392 KB Output is correct
20 Correct 2664 ms 150264 KB Output is correct
21 Correct 747 ms 147172 KB Output is correct
22 Correct 3070 ms 152184 KB Output is correct
23 Correct 813 ms 155200 KB Output is correct
24 Correct 1952 ms 153152 KB Output is correct
25 Correct 2986 ms 154988 KB Output is correct
26 Correct 2776 ms 154360 KB Output is correct
27 Correct 2534 ms 153696 KB Output is correct
28 Correct 1174 ms 239868 KB Output is correct
29 Correct 2868 ms 251940 KB Output is correct
30 Correct 7599 ms 214380 KB Output is correct
31 Correct 6767 ms 197880 KB Output is correct
32 Correct 782 ms 145928 KB Output is correct
33 Correct 999 ms 146860 KB Output is correct
34 Correct 1574 ms 248956 KB Output is correct
35 Correct 2246 ms 198392 KB Output is correct
36 Correct 4559 ms 249468 KB Output is correct
37 Correct 3613 ms 249684 KB Output is correct
38 Correct 3600 ms 249056 KB Output is correct
39 Runtime error 863 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -