oj.uz

Submission #122044

# Submission time Handle Problem Language Result Execution time Memory
122044 2019-06-27T12:44:37 Z yusufake Game (IOI13_game) C++
80 / 100
 7312 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 * 25 * 25;
 
int Y[N],L[N],R[N],id=-1;
ll s[N];

//vector<int> Y,L,R; 
//vector<ll> s;

// 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;
} 

int nevv(){
    return ++id;
    //s.pb(0); L.pb(0); R.pb(0); Y.pb(0);
    //return (int)s.size()-1;    
}

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(tl == tr){
		s[v] = t == -1 ? gcd(s[r1] , s[r2]) : t;
		return;
	}
	if(posy > tm) { if(!R[v]) R[v] = nevv(); up_y(sag,posy,R[r1],R[r2],t); }
	else          { if(!L[v]) L[v] = nevv(); 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(tl < tr){
		if(posx > tm) { if(!R[v]) R[v] = nevv(); up_x(sag,posx,posy,t); }
		else          { if(!L[v]) L[v] = nevv(); up_x(sol,posx,posy,t); }
	}
	if(!Y[v]) Y[v] = nevv();
	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) {
//    s.clear();
//    Y.clear();
//    L.clear();
//    R.clear();
    nevv();
    nevv();
}

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:49: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:49: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:54: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:54: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:62:12: note: in expansion of macro 'tm'
  if(posy > tm) { if(!R[v]) R[v] = nevv(); 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:62:48: note: in expansion of macro 'sag'
  if(posy > tm) { if(!R[v]) R[v] = nevv(); 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:63:48: note: in expansion of macro 'sol'
  else          { if(!L[v]) L[v] = nevv(); up_y(sol,posy,L[r1],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:68:13: note: in expansion of macro 'tm'
   if(posx > tm) { if(!R[v]) R[v] = nevv(); 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:68:49: note: in expansion of macro 'sag'
   if(posx > tm) { if(!R[v]) R[v] = nevv(); 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:69:49: note: in expansion of macro 'sol'
   else          { if(!L[v]) L[v] = nevv(); up_x(sol,posx,posy,t); }
                                                 ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 4 ms 640 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 640 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 2 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 1059 ms 28048 KB Output is correct
5 Correct 807 ms 28264 KB Output is correct
6 Correct 1177 ms 25600 KB Output is correct
7 Correct 1220 ms 25300 KB Output is correct
8 Correct 809 ms 16376 KB Output is correct
9 Correct 1419 ms 25336 KB Output is correct
10 Correct 1177 ms 25080 KB Output is correct
11 Correct 2 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 4 ms 612 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 4 ms 512 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 4 ms 640 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 512 KB Output is correct
12 Correct 1659 ms 13320 KB Output is correct
13 Correct 2443 ms 6892 KB Output is correct
14 Correct 607 ms 2084 KB Output is correct
15 Correct 2795 ms 9960 KB Output is correct
16 Correct 668 ms 15468 KB Output is correct
17 Correct 1725 ms 11764 KB Output is correct
18 Correct 3179 ms 15852 KB Output is correct
19 Correct 2780 ms 16000 KB Output is correct
20 Correct 2458 ms 15580 KB Output is correct
21 Correct 2 ms 384 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 4 ms 640 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 640 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 2 ms 384 KB Output is correct
12 Correct 1126 ms 28352 KB Output is correct
13 Correct 889 ms 28348 KB Output is correct
14 Correct 1270 ms 25596 KB Output is correct
15 Correct 1294 ms 25224 KB Output is correct
16 Correct 858 ms 16516 KB Output is correct
17 Correct 1421 ms 25476 KB Output is correct
18 Correct 1182 ms 24956 KB Output is correct
19 Correct 1640 ms 13404 KB Output is correct
20 Correct 2444 ms 6612 KB Output is correct
21 Correct 613 ms 2288 KB Output is correct
22 Correct 2910 ms 9988 KB Output is correct
23 Correct 675 ms 15480 KB Output is correct
24 Correct 1895 ms 11896 KB Output is correct
25 Correct 3096 ms 16000 KB Output is correct
26 Correct 2728 ms 16164 KB Output is correct
27 Correct 2377 ms 15468 KB Output is correct
28 Correct 1211 ms 158620 KB Output is correct
29 Correct 3012 ms 177004 KB Output is correct
30 Correct 7147 ms 120948 KB Output is correct
31 Correct 6682 ms 92820 KB Output is correct
32 Correct 673 ms 2144 KB Output is correct
33 Correct 890 ms 3960 KB Output is correct
34 Correct 1630 ms 173968 KB Output is correct
35 Correct 2258 ms 88988 KB Output is correct
36 Correct 4431 ms 174440 KB Output is correct
37 Correct 3839 ms 174108 KB Output is correct
38 Correct 3597 ms 173660 KB Output is correct
39 Correct 2829 ms 134280 KB Output is correct
40 Correct 2 ms 384 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 4 ms 512 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 4 ms 512 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 3 ms 512 KB Output is correct
10 Correct 3 ms 512 KB Output is correct
11 Correct 3 ms 384 KB Output is correct
12 Correct 1104 ms 28884 KB Output is correct
13 Correct 834 ms 29176 KB Output is correct
14 Correct 1312 ms 25756 KB Output is correct
15 Correct 1397 ms 25212 KB Output is correct
16 Correct 895 ms 16504 KB Output is correct
17 Correct 1416 ms 25568 KB Output is correct
18 Correct 1201 ms 25044 KB Output is correct
19 Correct 1660 ms 14088 KB Output is correct
20 Correct 2460 ms 7092 KB Output is correct
21 Correct 616 ms 2084 KB Output is correct
22 Correct 2920 ms 9872 KB Output is correct
23 Correct 687 ms 15652 KB Output is correct
24 Correct 1806 ms 11824 KB Output is correct
25 Correct 2894 ms 16028 KB Output is correct
26 Correct 2471 ms 15912 KB Output is correct
27 Correct 2321 ms 15504 KB Output is correct
28 Correct 1104 ms 158708 KB Output is correct
29 Correct 2937 ms 177320 KB Output is correct
30 Correct 7312 ms 121268 KB Output is correct
31 Correct 7137 ms 92704 KB Output is correct
32 Correct 705 ms 2168 KB Output is correct
33 Correct 951 ms 3800 KB Output is correct
34 Correct 1546 ms 173872 KB Output is correct
35 Correct 2328 ms 89040 KB Output is correct
36 Correct 4561 ms 174308 KB Output is correct
37 Correct 3648 ms 174552 KB Output is correct
38 Correct 3611 ms 173692 KB Output is correct
39 Runtime error 1192 ms 256000 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -