oj.uz

Submission #43159

# Submission time Handle Problem Language Result Execution time Memory
43159 2018-03-09T16:34:29 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;
typedef pair < int , int > pp;
 
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;
    struct node *l, *r, *to_y;
    node() { x = 0;  l = r = to_y = NULL; }

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

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

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 'll node::qry_y(int, int, int, int)':
game.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:32:32: note: in expansion of macro 'tm'
     return gcd(l ? l->qry_y(tl,tm,ly,ry) : 0 , r ? r->qry_y(tm+1,tr,ly,ry) : 0);
                                ^
game.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:32:61: note: in expansion of macro 'tm'
     return gcd(l ? l->qry_y(tl,tm,ly,ry) : 0 , r ? r->qry_y(tm+1,tr,ly,ry) : 0);
                                                             ^
game.cpp: In member function 'll node::qry_x(int, int, int, int, int, int)':
game.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:37:32: note: in expansion of macro 'tm'
     return gcd(l ? l->qry_x(tl,tm,lx,rx,ly,ry) : 0 , r ? r->qry_x(tm+1,tr,lx,rx,ly,ry) : 0);
                                ^
game.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:37:67: note: in expansion of macro 'tm'
     return gcd(l ? l->qry_x(tl,tm,lx,rx,ly,ry) : 0 , r ? r->qry_x(tm+1,tr,lx,rx,ly,ry) : 0);
                                                                   ^
game.cpp: In member function 'void node::up_y(int, int, int, ll)':
game.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:42:14: note: in expansion of macro 'tm'
      if(py > tm) { if(r == NULL) r = new node; r -> up_y(tm+1,tr,py,val); }
              ^
game.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:42:58: note: in expansion of macro 'tm'
      if(py > tm) { if(r == NULL) r = new node; r -> up_y(tm+1,tr,py,val); }
                                                          ^
game.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:43:61: note: in expansion of macro 'tm'
      else        { if(l == NULL) l = new node; l -> up_y(tl,tm,py,val); }
                                                             ^
game.cpp: In member function 'void node::up_x(int, int, int, int, ll)':
game.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:48:15: note: in expansion of macro 'tm'
       if(px > tm) { if(r == NULL) r = new node; r -> up_x(tm+1,tr,px,py,val); }
               ^
game.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:48:59: note: in expansion of macro 'tm'
       if(px > tm) { if(r == NULL) r = new node; r -> up_x(tm+1,tr,px,py,val); }
                                                           ^
game.cpp:6:16: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
 #define tm  (tl+tr >> 1)
                ^
game.cpp:49:62: note: in expansion of macro 'tm'
       else        { if(l == NULL) l = new node; l -> up_x(tl,tm,px,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 992 KB Output is correct
3 Correct 5 ms 1100 KB Output is correct
4 Correct 2 ms 1100 KB Output is correct
5 Correct 2 ms 1100 KB Output is correct
6 Correct 5 ms 1148 KB Output is correct
7 Correct 2 ms 1148 KB Output is correct
8 Correct 2 ms 1148 KB Output is correct
9 Correct 4 ms 1148 KB Output is correct
10 Correct 3 ms 1148 KB Output is correct
11 Correct 3 ms 1148 KB Output is correct
12 Correct 2 ms 1148 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1148 KB Output is correct
2 Correct 2 ms 1148 KB Output is correct
3 Correct 2 ms 1148 KB Output is correct
4 Correct 1333 ms 78152 KB Output is correct
5 Correct 1026 ms 82020 KB Output is correct
6 Correct 1631 ms 84100 KB Output is correct
7 Correct 1646 ms 88428 KB Output is correct
8 Correct 1018 ms 88428 KB Output is correct
9 Correct 1620 ms 97888 KB Output is correct
10 Correct 1489 ms 101824 KB Output is correct
11 Correct 2 ms 101824 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 101824 KB Output is correct
2 Correct 5 ms 101824 KB Output is correct
3 Correct 5 ms 101824 KB Output is correct
4 Correct 1 ms 101824 KB Output is correct
5 Correct 1 ms 101824 KB Output is correct
6 Correct 5 ms 101824 KB Output is correct
7 Correct 2 ms 101824 KB Output is correct
8 Correct 2 ms 101824 KB Output is correct
9 Correct 4 ms 101824 KB Output is correct
10 Correct 4 ms 101824 KB Output is correct
11 Correct 3 ms 101824 KB Output is correct
12 Correct 1960 ms 101824 KB Output is correct
13 Correct 2868 ms 101824 KB Output is correct
14 Correct 739 ms 101824 KB Output is correct
15 Correct 3285 ms 101824 KB Output is correct
16 Correct 844 ms 101824 KB Output is correct
17 Correct 2262 ms 101824 KB Output is correct
18 Correct 3731 ms 101824 KB Output is correct
19 Correct 4029 ms 103608 KB Output is correct
20 Correct 3434 ms 108312 KB Output is correct
21 Correct 2 ms 108312 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 108312 KB Output is correct
2 Correct 5 ms 108312 KB Output is correct
3 Correct 5 ms 108312 KB Output is correct
4 Correct 2 ms 108312 KB Output is correct
5 Correct 2 ms 108312 KB Output is correct
6 Correct 5 ms 108312 KB Output is correct
7 Correct 2 ms 108312 KB Output is correct
8 Correct 2 ms 108312 KB Output is correct
9 Correct 5 ms 108312 KB Output is correct
10 Correct 3 ms 108312 KB Output is correct
11 Correct 3 ms 108312 KB Output is correct
12 Correct 1346 ms 151580 KB Output is correct
13 Correct 1080 ms 155700 KB Output is correct
14 Correct 1680 ms 157504 KB Output is correct
15 Correct 1671 ms 162032 KB Output is correct
16 Correct 1055 ms 162032 KB Output is correct
17 Correct 1691 ms 171312 KB Output is correct
18 Correct 1525 ms 175312 KB Output is correct
19 Correct 1830 ms 175312 KB Output is correct
20 Correct 2687 ms 175312 KB Output is correct
21 Correct 700 ms 175312 KB Output is correct
22 Correct 3235 ms 175312 KB Output is correct
23 Correct 834 ms 175312 KB Output is correct
24 Correct 2319 ms 175312 KB Output is correct
25 Correct 3881 ms 175312 KB Output is correct
26 Correct 3579 ms 177104 KB Output is correct
27 Correct 3243 ms 181888 KB Output is correct
28 Execution timed out 13063 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 4 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 1454 ms 256000 KB Output is correct
13 Correct 1149 ms 256000 KB Output is correct
14 Correct 1660 ms 256000 KB Output is correct
15 Correct 1669 ms 256000 KB Output is correct
16 Correct 1000 ms 256000 KB Output is correct
17 Correct 1720 ms 256000 KB Output is correct
18 Correct 1557 ms 256000 KB Output is correct
19 Correct 1960 ms 256000 KB Output is correct
20 Correct 2877 ms 256000 KB Output is correct
21 Correct 738 ms 256000 KB Output is correct
22 Correct 3349 ms 256000 KB Output is correct
23 Correct 865 ms 256000 KB Output is correct
24 Correct 2412 ms 256000 KB Output is correct
25 Correct 4198 ms 256000 KB Output is correct
26 Correct 3682 ms 256000 KB Output is correct
27 Correct 3204 ms 256000 KB Output is correct
28 Execution timed out 13123 ms 256000 KB Time limit exceeded
29 Halted 0 ms 0 KB -