oj.uz

Submission #43173

# Submission time Handle Problem Language Result Execution time Memory
43173 2018-03-09T18:09:53 Z yusufake Game (IOI13_game) C++
63 / 100
 13000 ms 256000 KB 
#include<bits/stdc++.h>
#include "game.h"

using namespace std;
 
#define tm  (tl+tr >> 1)
#define mp make_pair
#define pb push_back
#define st first
#define nd second
 
typedef long long ll;

const int mod = 1e9 + 7;
const int N   = 2e5 + 5;
 
inline ll gcd(ll u, ll v) {
    ll r;
    while (v != 0) { r = u % v; u = v; v = r; }
    return u;
}

struct node{
    ll x;
    int tl, tr;
    struct node *l, *r, *to_y;
    node() { x = 0;  l = r = to_y = NULL; }
    node* nw(int l, int r){
        node* p = (node*) malloc(sizeof(node));
        p -> tl = l;  p -> tr = r;
        return p;
    }

    ll qry_y(int ly, int ry) { 
	   if(ly > tr || ry < tl) return 0;
	   if (ly <= tl && tr <= ry) return x;
	   return gcd(l ? l->qry_y(ly,ry) : 0 , r ? r->qry_y(ly,ry) : 0);
    }
    ll qry_x(int lx, int rx, int ly, int ry) { 
	   if(lx > tr || rx < tl) return 0;
	   if (lx <= tl && tr <= rx) return to_y ? to_y->qry_y(ly,ry) : 0;
	   return gcd(l ? l->qry_x(lx,rx,ly,ry) : 0 , r ? r->qry_x(lx,rx,ly,ry) : 0);
    }
 
    void up_y(int py, ll val){  
	    if(tl == tr){ x = val; return; }
	    if(py > tm) { if(r == NULL) r = nw(tm+1,tr); r -> up_y(py,val); }
	    else        { if(l == NULL) l = nw(tl,tm); l -> up_y(py,val); }
        x = gcd(l ? l->x : 0 , r ? r->x : 0);
    }
    void up_x(int px, int py, ll val){
	    if(tl < tr){
		    if(px > tm) { if(r == NULL) r = nw(tm+1,tr); r -> up_x(px,py,val); }
		    else        { if(l == NULL) l = nw(tl,tm);   l -> up_x(px,py,val); }
	        val = gcd(l ? l->to_y->qry_y(py,py) : 0 , r ? r->to_y->qry_y(py,py) : 0);
        }
	    if(to_y == NULL) to_y = nw(0,mod); to_y -> up_y(py,val);
    }
} root;  

void update(int x, int y, ll val){
	root.up_x(x,y,val);
}	
ll calculate(int lx, int ly, int rx, int ry){
	return root.qry_x(lx,rx,ly,ry);
}	
 
void init(int a, int b) { root.tl = 0; root.tr = mod; }

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 member function 'void node::up_y(int, ll)':
game.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:47:14: note: in expansion of macro 'tm'
      if(py > tm) { if(r == NULL) r = nw(tm+1,tr); r -> up_y(py,val); }
              ^
game.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:47:41: note: in expansion of macro 'tm'
      if(py > tm) { if(r == NULL) r = nw(tm+1,tr); r -> up_y(py,val); }
                                         ^
game.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:48:44: note: in expansion of macro 'tm'
      else        { if(l == NULL) l = nw(tl,tm); l -> up_y(py,val); }
                                            ^
game.cpp: In member function 'void node::up_x(int, int, ll)':
game.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:53:15: note: in expansion of macro 'tm'
       if(px > tm) { if(r == NULL) r = nw(tm+1,tr); r -> up_x(px,py,val); }
               ^
game.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:53:42: note: in expansion of macro 'tm'
       if(px > tm) { if(r == NULL) r = nw(tm+1,tr); r -> up_x(px,py,val); }
                                          ^
game.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:54:45: note: in expansion of macro 'tm'
       else        { if(l == NULL) l = nw(tl,tm);   l -> up_x(px,py,val); }
                                             ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 7 ms 864 KB Output is correct
3 Correct 6 ms 904 KB Output is correct
4 Correct 2 ms 904 KB Output is correct
5 Correct 2 ms 904 KB Output is correct
6 Correct 5 ms 932 KB Output is correct
7 Correct 2 ms 932 KB Output is correct
8 Correct 2 ms 932 KB Output is correct
9 Correct 4 ms 1072 KB Output is correct
10 Correct 3 ms 1072 KB Output is correct
11 Correct 3 ms 1072 KB Output is correct
12 Correct 1 ms 1072 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1072 KB Output is correct
2 Correct 2 ms 1072 KB Output is correct
3 Correct 2 ms 1072 KB Output is correct
4 Correct 1272 ms 77964 KB Output is correct
5 Correct 955 ms 81884 KB Output is correct
6 Correct 1565 ms 84088 KB Output is correct
7 Correct 1689 ms 88336 KB Output is correct
8 Correct 1000 ms 88336 KB Output is correct
9 Correct 1701 ms 97816 KB Output is correct
10 Correct 1461 ms 101636 KB Output is correct
11 Correct 2 ms 101636 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 101636 KB Output is correct
2 Correct 6 ms 101636 KB Output is correct
3 Correct 5 ms 101636 KB Output is correct
4 Correct 2 ms 101636 KB Output is correct
5 Correct 1 ms 101636 KB Output is correct
6 Correct 5 ms 101636 KB Output is correct
7 Correct 2 ms 101636 KB Output is correct
8 Correct 2 ms 101636 KB Output is correct
9 Correct 4 ms 101636 KB Output is correct
10 Correct 3 ms 101636 KB Output is correct
11 Correct 3 ms 101636 KB Output is correct
12 Correct 1948 ms 101636 KB Output is correct
13 Correct 2897 ms 101636 KB Output is correct
14 Correct 739 ms 101636 KB Output is correct
15 Correct 3298 ms 101636 KB Output is correct
16 Correct 779 ms 101636 KB Output is correct
17 Correct 2293 ms 101636 KB Output is correct
18 Correct 3654 ms 101636 KB Output is correct
19 Correct 3346 ms 103448 KB Output is correct
20 Correct 3099 ms 108080 KB Output is correct
21 Correct 2 ms 108080 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 108080 KB Output is correct
2 Correct 5 ms 108080 KB Output is correct
3 Correct 5 ms 108080 KB Output is correct
4 Correct 1 ms 108080 KB Output is correct
5 Correct 1 ms 108080 KB Output is correct
6 Correct 5 ms 108080 KB Output is correct
7 Correct 2 ms 108080 KB Output is correct
8 Correct 2 ms 108080 KB Output is correct
9 Correct 6 ms 108080 KB Output is correct
10 Correct 3 ms 108080 KB Output is correct
11 Correct 3 ms 108080 KB Output is correct
12 Correct 1294 ms 151260 KB Output is correct
13 Correct 1035 ms 155520 KB Output is correct
14 Correct 1519 ms 157324 KB Output is correct
15 Correct 1538 ms 161688 KB Output is correct
16 Correct 937 ms 161688 KB Output is correct
17 Correct 1568 ms 170904 KB Output is correct
18 Correct 1533 ms 174948 KB Output is correct
19 Correct 1917 ms 174948 KB Output is correct
20 Correct 2888 ms 174948 KB Output is correct
21 Correct 733 ms 174948 KB Output is correct
22 Correct 3158 ms 174948 KB Output is correct
23 Correct 769 ms 174948 KB Output is correct
24 Correct 2231 ms 174948 KB Output is correct
25 Correct 3666 ms 174948 KB Output is correct
26 Correct 3238 ms 176848 KB Output is correct
27 Correct 3108 ms 181376 KB Output is correct
28 Execution timed out 13080 ms 256000 KB Time limit exceeded
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 5 ms 256000 KB Output is correct
3 Correct 6 ms 256000 KB Output is correct
4 Correct 2 ms 256000 KB Output is correct
5 Correct 2 ms 256000 KB Output is correct
6 Correct 5 ms 256000 KB Output is correct
7 Correct 2 ms 256000 KB Output is correct
8 Correct 2 ms 256000 KB Output is correct
9 Correct 5 ms 256000 KB Output is correct
10 Correct 3 ms 256000 KB Output is correct
11 Correct 3 ms 256000 KB Output is correct
12 Correct 1377 ms 256000 KB Output is correct
13 Correct 1051 ms 256000 KB Output is correct
14 Correct 1568 ms 256000 KB Output is correct
15 Correct 1631 ms 256000 KB Output is correct
16 Correct 953 ms 256000 KB Output is correct
17 Correct 1600 ms 256000 KB Output is correct
18 Correct 1501 ms 256000 KB Output is correct
19 Correct 1964 ms 256000 KB Output is correct
20 Correct 2994 ms 256000 KB Output is correct
21 Correct 741 ms 256000 KB Output is correct
22 Correct 3293 ms 256000 KB Output is correct
23 Correct 808 ms 256000 KB Output is correct
24 Correct 2298 ms 256000 KB Output is correct
25 Correct 3665 ms 256000 KB Output is correct
26 Correct 3179 ms 256000 KB Output is correct
27 Correct 2995 ms 256000 KB Output is correct
28 Execution timed out 13062 ms 256000 KB Time limit exceeded
29 Halted 0 ms 0 KB -