oj.uz

Submission #43174

# Submission time Handle Problem Language Result Execution time Memory
43174 2018-03-09T18:31:22 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() { x = 0;  l = r = to_y = NULL; }
} root;  
node* nw(int l, int r){
    node* p = (node*) malloc(sizeof(node));
    p -> tl = l;  p -> tr = r;
    return p;
}

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


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.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 function 'void up_y(node&, int, ll)':
game.cpp:6:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (p.tl+p.tr >> 1)
                  ^
game.cpp:48:14: note: in expansion of macro 'tm'
      if(py > tm) { if(p.r == NULL) p.r = nw(tm+1,p.tr); up_y(*p.r,py,val); }
              ^
game.cpp:6:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (p.tl+p.tr >> 1)
                  ^
game.cpp:48:45: note: in expansion of macro 'tm'
      if(py > tm) { if(p.r == NULL) p.r = nw(tm+1,p.tr); up_y(*p.r,py,val); }
                                             ^
game.cpp:6:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (p.tl+p.tr >> 1)
                  ^
game.cpp:49:50: note: in expansion of macro 'tm'
      else        { if(p.l == NULL) p.l = nw(p.tl,tm);   up_y(*p.l,py,val); }
                                                  ^
game.cpp: In function 'void up_x(node&, int, int, ll)':
game.cpp:6:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (p.tl+p.tr >> 1)
                  ^
game.cpp:54:15: note: in expansion of macro 'tm'
       if(px > tm) { if(p.r == NULL) p.r = nw(tm+1,p.tr); up_x(*p.r,px,py,val); }
               ^
game.cpp:6:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (p.tl+p.tr >> 1)
                  ^
game.cpp:54:46: note: in expansion of macro 'tm'
       if(px > tm) { if(p.r == NULL) p.r = nw(tm+1,p.tr); up_x(*p.r,px,py,val); }
                                              ^
game.cpp:6:18: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (p.tl+p.tr >> 1)
                  ^
game.cpp:55:51: note: in expansion of macro 'tm'
       else        { if(p.l == NULL) p.l = nw(p.tl,tm);   up_x(*p.l,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 5 ms 864 KB Output is correct
3 Correct 5 ms 940 KB Output is correct
4 Correct 1 ms 940 KB Output is correct
5 Correct 1 ms 940 KB Output is correct
6 Correct 5 ms 980 KB Output is correct
7 Correct 2 ms 980 KB Output is correct
8 Correct 2 ms 980 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 2 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 1384 ms 78020 KB Output is correct
5 Correct 1048 ms 82192 KB Output is correct
6 Correct 1550 ms 83968 KB Output is correct
7 Correct 1687 ms 88424 KB Output is correct
8 Correct 996 ms 88424 KB Output is correct
9 Correct 1670 ms 97824 KB Output is correct
10 Correct 1602 ms 101692 KB Output is correct
11 Correct 2 ms 101692 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 101692 KB Output is correct
2 Correct 5 ms 101692 KB Output is correct
3 Correct 5 ms 101692 KB Output is correct
4 Correct 2 ms 101692 KB Output is correct
5 Correct 2 ms 101692 KB Output is correct
6 Correct 7 ms 101692 KB Output is correct
7 Correct 2 ms 101692 KB Output is correct
8 Correct 2 ms 101692 KB Output is correct
9 Correct 5 ms 101692 KB Output is correct
10 Correct 3 ms 101692 KB Output is correct
11 Correct 3 ms 101692 KB Output is correct
12 Correct 2077 ms 101692 KB Output is correct
13 Correct 3030 ms 101692 KB Output is correct
14 Correct 779 ms 101692 KB Output is correct
15 Correct 3455 ms 101692 KB Output is correct
16 Correct 853 ms 101692 KB Output is correct
17 Correct 2127 ms 101692 KB Output is correct
18 Correct 3668 ms 101692 KB Output is correct
19 Correct 3193 ms 103464 KB Output is correct
20 Correct 2925 ms 108136 KB Output is correct
21 Correct 2 ms 108136 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 108136 KB Output is correct
2 Correct 5 ms 108136 KB Output is correct
3 Correct 5 ms 108136 KB Output is correct
4 Correct 2 ms 108136 KB Output is correct
5 Correct 2 ms 108136 KB Output is correct
6 Correct 5 ms 108136 KB Output is correct
7 Correct 2 ms 108136 KB Output is correct
8 Correct 2 ms 108136 KB Output is correct
9 Correct 5 ms 108136 KB Output is correct
10 Correct 3 ms 108136 KB Output is correct
11 Correct 3 ms 108136 KB Output is correct
12 Correct 1475 ms 151312 KB Output is correct
13 Correct 1134 ms 155376 KB Output is correct
14 Correct 1580 ms 157348 KB Output is correct
15 Correct 1648 ms 161764 KB Output is correct
16 Correct 983 ms 161764 KB Output is correct
17 Correct 1631 ms 171104 KB Output is correct
18 Correct 1510 ms 175004 KB Output is correct
19 Correct 2064 ms 175004 KB Output is correct
20 Correct 3029 ms 175004 KB Output is correct
21 Correct 763 ms 175004 KB Output is correct
22 Correct 3470 ms 175004 KB Output is correct
23 Correct 1014 ms 175004 KB Output is correct
24 Correct 2261 ms 175004 KB Output is correct
25 Correct 3926 ms 175004 KB Output is correct
26 Correct 3279 ms 176652 KB Output is correct
27 Correct 2999 ms 181248 KB Output is correct
28 Execution timed out 13062 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 5 ms 256000 KB Output is correct
4 Correct 2 ms 256000 KB Output is correct
5 Correct 1 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 1352 ms 256000 KB Output is correct
13 Correct 1068 ms 256000 KB Output is correct
14 Correct 1583 ms 256000 KB Output is correct
15 Correct 1617 ms 256000 KB Output is correct
16 Correct 970 ms 256000 KB Output is correct
17 Correct 1619 ms 256000 KB Output is correct
18 Correct 1587 ms 256000 KB Output is correct
19 Correct 2007 ms 256000 KB Output is correct
20 Correct 2994 ms 256000 KB Output is correct
21 Correct 752 ms 256000 KB Output is correct
22 Correct 3394 ms 256000 KB Output is correct
23 Correct 833 ms 256000 KB Output is correct
24 Correct 2236 ms 256000 KB Output is correct
25 Correct 3776 ms 256000 KB Output is correct
26 Correct 3252 ms 256000 KB Output is correct
27 Correct 3081 ms 256000 KB Output is correct
28 Execution timed out 13093 ms 256000 KB Time limit exceeded
29 Halted 0 ms 0 KB -