oj.uz

Submission #43176

# Submission time Handle Problem Language Result Execution time Memory
43176 2018-03-09T19:00:42 Z yusufake Game (IOI13_game) C++
63 / 100
 13000 ms 256000 KB 
#include<bits/stdc++.h>
#include "game.h"
 
using namespace std;
  
typedef long long ll;
 
const int mod = 1e9 + 7;
const int N   = 2e5 + 5;
 
long long gcd(long long X, long long Y) {
    if(X == 0 || Y == 0) {
        return X + Y;
    }

    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
} 
struct node{
    ll x;
    int tl, tr;
    struct node *l, *r, *to_y;
    node(int a, int b) { tl = a; tr = b; x = 0;  l = r = to_y = NULL; }
};  

    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){  
	    int tm = p->tl + p->tr >> 1;
		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){
	    int tm = p->tl + p->tr >> 1;
		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); }

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:43:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
      int tm = p->tl + p->tr >> 1;
                     ^
game.cpp: In function 'void up_x(node*, int, int, ll)':
game.cpp:50:21: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
      int tm = p->tl + p->tr >> 1;
                     ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 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 2 ms 940 KB Output is correct
5 Correct 1 ms 940 KB Output is correct
6 Correct 5 ms 1096 KB Output is correct
7 Correct 2 ms 1096 KB Output is correct
8 Correct 2 ms 1096 KB Output is correct
9 Correct 4 ms 1108 KB Output is correct
10 Correct 3 ms 1108 KB Output is correct
11 Correct 3 ms 1108 KB Output is correct
12 Correct 2 ms 1108 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1108 KB Output is correct
2 Correct 2 ms 1108 KB Output is correct
3 Correct 2 ms 1108 KB Output is correct
4 Correct 1245 ms 78148 KB Output is correct
5 Correct 867 ms 81852 KB Output is correct
6 Correct 1515 ms 84016 KB Output is correct
7 Correct 1564 ms 88456 KB Output is correct
8 Correct 948 ms 88456 KB Output is correct
9 Correct 1566 ms 97784 KB Output is correct
10 Correct 1365 ms 101848 KB Output is correct
11 Correct 2 ms 101848 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 101848 KB Output is correct
2 Correct 5 ms 101848 KB Output is correct
3 Correct 5 ms 101848 KB Output is correct
4 Correct 2 ms 101848 KB Output is correct
5 Correct 1 ms 101848 KB Output is correct
6 Correct 5 ms 101848 KB Output is correct
7 Correct 2 ms 101848 KB Output is correct
8 Correct 2 ms 101848 KB Output is correct
9 Correct 4 ms 101848 KB Output is correct
10 Correct 3 ms 101848 KB Output is correct
11 Correct 3 ms 101848 KB Output is correct
12 Correct 1792 ms 101848 KB Output is correct
13 Correct 2987 ms 101848 KB Output is correct
14 Correct 722 ms 101848 KB Output is correct
15 Correct 3468 ms 101848 KB Output is correct
16 Correct 762 ms 101848 KB Output is correct
17 Correct 2254 ms 101848 KB Output is correct
18 Correct 3751 ms 101848 KB Output is correct
19 Correct 3224 ms 103604 KB Output is correct
20 Correct 2871 ms 108168 KB Output is correct
21 Correct 2 ms 108168 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 108168 KB Output is correct
2 Correct 5 ms 108168 KB Output is correct
3 Correct 6 ms 108168 KB Output is correct
4 Correct 2 ms 108168 KB Output is correct
5 Correct 1 ms 108168 KB Output is correct
6 Correct 5 ms 108168 KB Output is correct
7 Correct 2 ms 108168 KB Output is correct
8 Correct 2 ms 108168 KB Output is correct
9 Correct 4 ms 108168 KB Output is correct
10 Correct 3 ms 108168 KB Output is correct
11 Correct 3 ms 108168 KB Output is correct
12 Correct 1240 ms 151456 KB Output is correct
13 Correct 895 ms 155524 KB Output is correct
14 Correct 1476 ms 157252 KB Output is correct
15 Correct 1548 ms 161700 KB Output is correct
16 Correct 951 ms 161700 KB Output is correct
17 Correct 1522 ms 171056 KB Output is correct
18 Correct 1404 ms 175064 KB Output is correct
19 Correct 1762 ms 175064 KB Output is correct
20 Correct 2954 ms 175064 KB Output is correct
21 Correct 730 ms 175064 KB Output is correct
22 Correct 3326 ms 175064 KB Output is correct
23 Correct 722 ms 175064 KB Output is correct
24 Correct 2147 ms 175064 KB Output is correct
25 Correct 3582 ms 175064 KB Output is correct
26 Correct 3180 ms 176740 KB Output is correct
27 Correct 2912 ms 181344 KB Output is correct
28 Execution timed out 13089 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 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 1192 ms 256000 KB Output is correct
13 Correct 915 ms 256000 KB Output is correct
14 Correct 1552 ms 256000 KB Output is correct
15 Correct 1535 ms 256000 KB Output is correct
16 Correct 927 ms 256000 KB Output is correct
17 Correct 1557 ms 256000 KB Output is correct
18 Correct 1376 ms 256000 KB Output is correct
19 Correct 1738 ms 256000 KB Output is correct
20 Correct 2957 ms 256000 KB Output is correct
21 Correct 744 ms 256000 KB Output is correct
22 Correct 3480 ms 256000 KB Output is correct
23 Correct 785 ms 256000 KB Output is correct
24 Correct 2200 ms 256000 KB Output is correct
25 Correct 3497 ms 256000 KB Output is correct
26 Correct 3062 ms 256000 KB Output is correct
27 Correct 2876 ms 256000 KB Output is correct
28 Execution timed out 13066 ms 256000 KB Time limit exceeded
29 Halted 0 ms 0 KB -