oj.uz

Submission #43175

# Submission time Handle Problem Language Result Execution time Memory
43175 2018-03-09T18:40:14 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; }
};  
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);
    }

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 = nw(0,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:19: 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:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (p->tl+p->tr >> 1)
                   ^
game.cpp:48:47: 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:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (p->tl+p->tr >> 1)
                   ^
game.cpp:49:53: 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:19: 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:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (p->tl+p->tr >> 1)
                   ^
game.cpp:54:48: 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:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (p->tl+p->tr >> 1)
                   ^
game.cpp:55:54: 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 6 ms 1032 KB Output is correct
4 Correct 2 ms 1032 KB Output is correct
5 Correct 2 ms 1032 KB Output is correct
6 Correct 5 ms 1112 KB Output is correct
7 Correct 2 ms 1112 KB Output is correct
8 Correct 2 ms 1112 KB Output is correct
9 Correct 5 ms 1112 KB Output is correct
10 Correct 3 ms 1112 KB Output is correct
11 Correct 3 ms 1112 KB Output is correct
12 Correct 2 ms 1112 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1112 KB Output is correct
2 Correct 2 ms 1112 KB Output is correct
3 Correct 2 ms 1112 KB Output is correct
4 Correct 1399 ms 78028 KB Output is correct
5 Correct 1064 ms 82056 KB Output is correct
6 Correct 1526 ms 83884 KB Output is correct
7 Correct 1592 ms 88380 KB Output is correct
8 Correct 943 ms 88380 KB Output is correct
9 Correct 1629 ms 97680 KB Output is correct
10 Correct 1541 ms 101736 KB Output is correct
11 Correct 2 ms 101736 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 101736 KB Output is correct
2 Correct 5 ms 101736 KB Output is correct
3 Correct 6 ms 101736 KB Output is correct
4 Correct 2 ms 101736 KB Output is correct
5 Correct 2 ms 101736 KB Output is correct
6 Correct 6 ms 101736 KB Output is correct
7 Correct 2 ms 101736 KB Output is correct
8 Correct 2 ms 101736 KB Output is correct
9 Correct 5 ms 101736 KB Output is correct
10 Correct 3 ms 101736 KB Output is correct
11 Correct 3 ms 101736 KB Output is correct
12 Correct 2031 ms 101736 KB Output is correct
13 Correct 3006 ms 101736 KB Output is correct
14 Correct 773 ms 101736 KB Output is correct
15 Correct 3435 ms 101736 KB Output is correct
16 Correct 902 ms 101736 KB Output is correct
17 Correct 2174 ms 101736 KB Output is correct
18 Correct 3539 ms 101736 KB Output is correct
19 Correct 3171 ms 103456 KB Output is correct
20 Correct 2973 ms 108228 KB Output is correct
21 Correct 2 ms 108228 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 108228 KB Output is correct
2 Correct 5 ms 108228 KB Output is correct
3 Correct 5 ms 108228 KB Output is correct
4 Correct 2 ms 108228 KB Output is correct
5 Correct 1 ms 108228 KB Output is correct
6 Correct 5 ms 108228 KB Output is correct
7 Correct 2 ms 108228 KB Output is correct
8 Correct 2 ms 108228 KB Output is correct
9 Correct 4 ms 108228 KB Output is correct
10 Correct 3 ms 108228 KB Output is correct
11 Correct 3 ms 108228 KB Output is correct
12 Correct 1441 ms 151500 KB Output is correct
13 Correct 982 ms 155376 KB Output is correct
14 Correct 1453 ms 157436 KB Output is correct
15 Correct 1535 ms 161764 KB Output is correct
16 Correct 1006 ms 161764 KB Output is correct
17 Correct 1606 ms 171044 KB Output is correct
18 Correct 1558 ms 174976 KB Output is correct
19 Correct 2041 ms 174976 KB Output is correct
20 Correct 2980 ms 174976 KB Output is correct
21 Correct 746 ms 174976 KB Output is correct
22 Correct 3400 ms 174976 KB Output is correct
23 Correct 842 ms 174976 KB Output is correct
24 Correct 2189 ms 174976 KB Output is correct
25 Correct 3677 ms 174976 KB Output is correct
26 Correct 3279 ms 176660 KB Output is correct
27 Correct 3013 ms 181352 KB Output is correct
28 Execution timed out 13094 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 6 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 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 1426 ms 256000 KB Output is correct
13 Correct 1038 ms 256000 KB Output is correct
14 Correct 1527 ms 256000 KB Output is correct
15 Correct 1600 ms 256000 KB Output is correct
16 Correct 1000 ms 256000 KB Output is correct
17 Correct 1625 ms 256000 KB Output is correct
18 Correct 1513 ms 256000 KB Output is correct
19 Correct 2028 ms 256000 KB Output is correct
20 Correct 2996 ms 256000 KB Output is correct
21 Correct 796 ms 256000 KB Output is correct
22 Correct 3507 ms 256000 KB Output is correct
23 Correct 916 ms 256000 KB Output is correct
24 Correct 2307 ms 256000 KB Output is correct
25 Correct 3826 ms 256000 KB Output is correct
26 Correct 3358 ms 256000 KB Output is correct
27 Correct 3123 ms 256000 KB Output is correct
28 Execution timed out 13054 ms 256000 KB Time limit exceeded
29 Halted 0 ms 0 KB -