oj.uz

Submission #44582

# Submission time Handle Problem Language Result Execution time Memory
44582 2018-04-03T12:28:05 Z yusufake Game (IOI13_game) C++
63 / 100
 13000 ms 256000 KB 
#include<bits/stdc++.h>
#include "game.h"
 
using namespace std;
 
#define tm  (p->tl+p->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(int a, int b) { x = 0;  tl = a; tr = b;  l = r = to_y = NULL; }
};  
 
    ll qry_y(node* p, int ly, int ry) { 
	   if(p == NULL || ly > p->tr || ry < p->tl) return 0;
	   if (ly <= p->tl && p->tr <= ry) return p->x;
	   return gcd(qry_y(p->l,ly,ry) , qry_y(p->r,ly,ry));
    }
    ll qry_x(node* p, int lx, int rx, int ly, int ry) { 
	   if(p == NULL || lx > p->tr || rx < p->tl) return 0;
	   if (lx <= p->tl && p->tr <= rx) return qry_y(p->to_y,ly,ry);
	   return gcd(qry_x(p->l,lx,rx,ly,ry) , qry_x(p->r,lx,rx,ly,ry));
    }
 
    void up_y(node* p, int py, ll val){  
	    if(p->tl == p->tr){ p->x = val; return; }
	    if(py > tm) { if(p->r == NULL) p->r = new node(tm+1,p->tr); up_y(p->r,py,val); }
	    else        { if(p->l == NULL) p->l = new node(p->tl,tm);   up_y(p->l,py,val); }
        p->x = gcd(p->l ? p->l->x : 0 , p->r ? p->r->x : 0);
    }
    void up_x(node* p, int px, int py, ll val){
	    if(p->tl < p->tr){
		    if(px > tm) { if(p->r == NULL) p->r = new node(tm+1,p->tr); up_x(p->r,px,py,val); }
		    else        { if(p->l == NULL) p->l = new node(p->tl,tm);   up_x(p->l,px,py,val); }
	        val = gcd(p->l ? qry_y(p->l->to_y,py,py) : 0 , p->r ? qry_y(p->r->to_y,py,py) : 0);
        }
	    if(p->to_y == NULL) p->to_y = new node(0,mod); up_y(p->to_y,py,val);
    }
 
node* root;
void update(int x, int y, ll val){
	up_x(root,x,y,val);
}	
ll calculate(int lx, int ly, int rx, int ry){
	return qry_x(root,lx,rx,ly,ry);
}	
 
void init(int a, int b) { root = new node(0,mod); }

//int main(){}

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 'void up_y(node*, int, ll)':
game.cpp:6:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (p->tl+p->tr >> 1)
              ~~~~~^~~~~
game.cpp:43:14: note: in expansion of macro 'tm'
      if(py > tm) { if(p->r == NULL) p->r = new node(tm+1,p->tr); up_y(p->r,py,val); }
              ^~
game.cpp:6:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (p->tl+p->tr >> 1)
              ~~~~~^~~~~
game.cpp:43:53: note: in expansion of macro 'tm'
      if(py > tm) { if(p->r == NULL) p->r = new node(tm+1,p->tr); up_y(p->r,py,val); }
                                                     ^~
game.cpp:6:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (p->tl+p->tr >> 1)
              ~~~~~^~~~~
game.cpp:44:59: note: in expansion of macro 'tm'
      else        { if(p->l == NULL) p->l = new node(p->tl,tm);   up_y(p->l,py,val); }
                                                           ^~
game.cpp: In function 'void up_x(node*, int, int, ll)':
game.cpp:6:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (p->tl+p->tr >> 1)
              ~~~~~^~~~~
game.cpp:49:15: note: in expansion of macro 'tm'
       if(px > tm) { if(p->r == NULL) p->r = new node(tm+1,p->tr); up_x(p->r,px,py,val); }
               ^~
game.cpp:6:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (p->tl+p->tr >> 1)
              ~~~~~^~~~~
game.cpp:49:54: note: in expansion of macro 'tm'
       if(px > tm) { if(p->r == NULL) p->r = new node(tm+1,p->tr); up_x(p->r,px,py,val); }
                                                      ^~
game.cpp:6:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (p->tl+p->tr >> 1)
              ~~~~~^~~~~
game.cpp:50:60: note: in expansion of macro 'tm'
       else        { if(p->l == NULL) p->l = new node(p->tl,tm);   up_x(p->l,px,py,val); }
                                                            ^~
game.cpp:53:6: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
      if(p->to_y == NULL) p->to_y = new node(0,mod); up_y(p->to_y,py,val);
      ^~
game.cpp:53:53: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
      if(p->to_y == NULL) p->to_y = new node(0,mod); up_y(p->to_y,py,val);
                                                     ^~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1084 KB Output is correct
2 Correct 2 ms 1084 KB Output is correct
3 Correct 2 ms 1084 KB Output is correct
4 Correct 1620 ms 75336 KB Output is correct
5 Correct 1272 ms 79196 KB Output is correct
6 Correct 1826 ms 81372 KB Output is correct
7 Correct 1967 ms 85836 KB Output is correct
8 Correct 1196 ms 85836 KB Output is correct
9 Correct 1799 ms 95064 KB Output is correct
10 Correct 1678 ms 98956 KB Output is correct
11 Correct 2 ms 98956 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 98956 KB Output is correct
2 Correct 6 ms 98956 KB Output is correct
3 Correct 6 ms 98956 KB Output is correct
4 Correct 2 ms 98956 KB Output is correct
5 Correct 2 ms 98956 KB Output is correct
6 Correct 7 ms 98956 KB Output is correct
7 Correct 3 ms 98956 KB Output is correct
8 Correct 2 ms 98956 KB Output is correct
9 Correct 5 ms 98956 KB Output is correct
10 Correct 3 ms 98956 KB Output is correct
11 Correct 4 ms 98956 KB Output is correct
12 Correct 2372 ms 98956 KB Output is correct
13 Correct 3530 ms 98956 KB Output is correct
14 Correct 888 ms 98956 KB Output is correct
15 Correct 3796 ms 98956 KB Output is correct
16 Correct 1012 ms 98956 KB Output is correct
17 Correct 2701 ms 98956 KB Output is correct
18 Correct 4311 ms 98956 KB Output is correct
19 Correct 3789 ms 98956 KB Output is correct
20 Correct 3719 ms 102988 KB Output is correct
21 Correct 2 ms 102988 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 102988 KB Output is correct
2 Correct 6 ms 102988 KB Output is correct
3 Correct 6 ms 102988 KB Output is correct
4 Correct 2 ms 102988 KB Output is correct
5 Correct 2 ms 102988 KB Output is correct
6 Correct 6 ms 102988 KB Output is correct
7 Correct 2 ms 102988 KB Output is correct
8 Correct 2 ms 102988 KB Output is correct
9 Correct 6 ms 102988 KB Output is correct
10 Correct 3 ms 102988 KB Output is correct
11 Correct 4 ms 102988 KB Output is correct
12 Correct 1533 ms 143452 KB Output is correct
13 Correct 1299 ms 147432 KB Output is correct
14 Correct 1828 ms 149596 KB Output is correct
15 Correct 1904 ms 154104 KB Output is correct
16 Correct 1071 ms 154104 KB Output is correct
17 Correct 1825 ms 163180 KB Output is correct
18 Correct 1861 ms 167404 KB Output is correct
19 Correct 2325 ms 167404 KB Output is correct
20 Correct 3520 ms 167404 KB Output is correct
21 Correct 894 ms 167404 KB Output is correct
22 Correct 4003 ms 167404 KB Output is correct
23 Correct 1131 ms 167404 KB Output is correct
24 Correct 2729 ms 167404 KB Output is correct
25 Correct 4545 ms 167404 KB Output is correct
26 Correct 3938 ms 169120 KB Output is correct
27 Correct 3853 ms 173820 KB Output is correct
28 Execution timed out 13079 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 3 ms 256000 KB Output is correct
2 Correct 6 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 6 ms 256000 KB Output is correct
7 Correct 3 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 1568 ms 256000 KB Output is correct
13 Correct 1171 ms 256000 KB Output is correct
14 Correct 1702 ms 256000 KB Output is correct
15 Correct 1828 ms 256000 KB Output is correct
16 Correct 1121 ms 256000 KB Output is correct
17 Correct 1842 ms 256000 KB Output is correct
18 Correct 1783 ms 256000 KB Output is correct
19 Correct 2351 ms 256000 KB Output is correct
20 Correct 3988 ms 256000 KB Output is correct
21 Correct 902 ms 256000 KB Output is correct
22 Correct 3884 ms 256000 KB Output is correct
23 Correct 1113 ms 256000 KB Output is correct
24 Correct 2824 ms 256000 KB Output is correct
25 Correct 4725 ms 256000 KB Output is correct
26 Correct 4369 ms 256000 KB Output is correct
27 Correct 4050 ms 256000 KB Output is correct
28 Execution timed out 13071 ms 256000 KB Time limit exceeded
29 Halted 0 ms 0 KB -