답안 #29171 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
29171	2017-07-18T13:33:26 Z	nibnalin	게임 (IOI13_game)	C++14	80 / 100	9299 ms	256000 KB

game

#include "bits/stdc++.h"
#include "game.h"
using namespace std;
inline long long gcd(long long a , long long b){
    while(b){
        long long temp = a - b * (a / b);
        a = b;
        b = temp;
    }
    return a;
}
int n , m , q , type , x , y , X , Y;
long long value;
struct node{
    long long val;
    node *left , *beech , *right;
    node(){
        val = 0LL;
        left = beech = right = NULL;
    }
    long long query(int l , int r , int ql , int qr){
        if(r < l || l > qr || r < ql)
            return 0LL;
        if(l >= ql && r <= qr)
            return val;
        int mid1 = l + (r - l + 1)/3 , mid2 = r - (r - l + 1)/3;
        return gcd((beech == NULL ) ? 0 : beech -> query(mid1 + 1 , mid2 , ql , qr) , gcd((left == NULL) ? 0 : left -> query(l , mid1 , ql , qr) ,(right == NULL) ? 0 : right -> query(mid2 + 1 , r , ql , qr)));
    }
    node* update(int l , int r , int idx , bool leaf , node *ll , node *bb , node*rr){
        if(l == r)
            if(leaf)
                val = value;
            else
                val = gcd((ll == NULL) ? 0 : ll -> val , gcd((bb == NULL) ? 0 : bb -> val , (rr == NULL) ? 0 : rr -> val));
        else{
            int mid1 = l + (r - l + 1) / 3 , mid2 = r - (r - l + 1) / 3;
            if(idx <= mid1){
                if(left == NULL)
                    left = new node();
                left = left -> update(l , mid1 , idx , leaf , (ll == NULL) ? NULL : ll -> left , (bb == NULL) ? NULL : bb -> left , (rr == NULL) ? NULL : rr -> left);
            }
            else if(idx <= mid2){
                if(beech == NULL)
                    beech = new node();
                beech = beech -> update(mid1 + 1 , mid2 , idx , leaf , (ll == NULL) ? NULL : ll -> beech , (bb == NULL) ? NULL : bb -> beech , (rr == NULL) ? NULL : rr -> beech);
            }
            else{
                if(right == NULL)
                    right = new node();
                right = right -> update(mid2 + 1 , r , idx , leaf , (ll == NULL) ? NULL : ll -> right , (bb == NULL) ? NULL : bb -> right , (rr == NULL) ? NULL : rr -> right);
            }
            val = gcd((beech == NULL) ? 0LL : beech -> val , gcd((left == NULL) ? 0LL : left -> val , (right == NULL) ? 0LL : right -> val));
        }
        return this;
    }
};
struct nodex{
    node *ychild;
    nodex *left , *beech , *right;
    nodex(){
        ychild = NULL;
        left = right = beech = NULL;
    }
    long long queryx(int l , int r , int x1 , int y1 , int x2 , int y2){
        if(r < l || l > x2 || r < x1 || ychild == NULL)
            return 0LL;
        if(l >= x1 && r <= x2)
            return ychild -> query(0 , m - 1 , y1 , y2);
        int mid1 = l + (r - l + 1)/3 , mid2 = r - (r - l + 1)/3;
        return gcd((beech == NULL) ? 0 : beech -> queryx(mid1 + 1 , mid2 , x1 , y1 , x2 , y2) , gcd((left == NULL) ? 0 : left -> queryx(l , mid1 , x1 , y1 , x2 , y2) ,(right == NULL) ? 0 :  right -> queryx(mid2 + 1 , r , x1 , y1 , x2 , y2)));
    }
    nodex* update(int l , int r , int idx , int idy){
        if(ychild == NULL)
            ychild = new node();
        if(l == r)
            ychild = ychild -> update(0 , m - 1 , idy , 1 , NULL , NULL , NULL);
        else{
            int mid1 = l + (r - l + 1)/3 , mid2 = r - (r - l + 1)/3;
            if(idx <= mid1){
                if(left == NULL)
                    left = new nodex();
                left = left -> update(l , mid1, idx , idy);
            }
            else if(idx <= mid2){
                if(beech == NULL)
                    beech = new nodex();
                beech = beech -> update(mid1 + 1 , mid2 , idx , idy);
            }
            else{
                if(right == NULL)
                    right = new nodex();
                right = right -> update(mid2 + 1 , r , idx , idy);
            }
            ychild = ychild -> update(0 , m - 1 , idy , 0 , (left == NULL) ? NULL : left -> ychild ,(beech == NULL) ? NULL : beech -> ychild ,(right == NULL) ? NULL :  right -> ychild);
        }
        return this;
    }
};
nodex * root = new nodex();
/*int main(){
    scanf("%d %d %d" , &n , &m , &q);
    while(~scanf("%d" , &type)){
        if(type & 1){
            scanf("%d %d %lld" , &x , &y , &value);
            root = root -> update(0 , n - 1 , x , y);
        }
        else{
            scanf("%d %d %d %d" , &x , &y , &X , &Y);
            printf("%lld\n" , root -> queryx(0 , n - 1 , x , y , X , Y));
        }
    }
}*/

void init(int R, int C) {
	n = R, m = C;
}
 
void update(int P, int Q, long long K) {
	//cout << "upd\n";
	value = K;
	root = root -> update(0 , n - 1 , P, Q);
}
 
long long calculate(int P, int Q, int U, int V) {
	//cout << "calc\n";
	return root -> queryx(0 , n - 1 , P , Q , U , V);
}

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;
      ^

Subtask #1
10.0 / 10.0

#	결과	메모리	Grader output
1	Correct	2084 KB	Output is correct
2	Correct	2216 KB	Output is correct
3	Correct	2216 KB	Output is correct
4	Correct	2084 KB	Output is correct
5	Correct	2084 KB	Output is correct
6	Correct	2216 KB	Output is correct
7	Correct	2084 KB	Output is correct
8	Correct	2084 KB	Output is correct
9	Correct	2216 KB	Output is correct
10	Correct	2084 KB	Output is correct
11	Correct	2084 KB	Output is correct
12	Correct	2084 KB	Output is correct

Subtask #2
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	2084 KB	Output is correct
2	Correct	0 ms	2084 KB	Output is correct
3	Correct	0 ms	2084 KB	Output is correct
4	Correct	1139 ms	9608 KB	Output is correct
5	Correct	713 ms	9608 KB	Output is correct
6	Correct	966 ms	9608 KB	Output is correct
7	Correct	1073 ms	9608 KB	Output is correct
8	Correct	779 ms	6308 KB	Output is correct
9	Correct	1193 ms	9740 KB	Output is correct
10	Correct	1043 ms	9608 KB	Output is correct
11	Correct	0 ms	2084 KB	Output is correct

Subtask #3
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	2084 KB	Output is correct
2	Correct	0 ms	2216 KB	Output is correct
3	Correct	0 ms	2216 KB	Output is correct
4	Correct	0 ms	2084 KB	Output is correct
5	Correct	0 ms	2084 KB	Output is correct
6	Correct	0 ms	2216 KB	Output is correct
7	Correct	0 ms	2084 KB	Output is correct
8	Correct	0 ms	2084 KB	Output is correct
9	Correct	0 ms	2216 KB	Output is correct
10	Correct	0 ms	2084 KB	Output is correct
11	Correct	0 ms	2084 KB	Output is correct
12	Correct	1963 ms	11324 KB	Output is correct
13	Correct	3329 ms	6440 KB	Output is correct
14	Correct	539 ms	2216 KB	Output is correct
15	Correct	4093 ms	8948 KB	Output is correct
16	Correct	213 ms	16472 KB	Output is correct
17	Correct	1673 ms	10268 KB	Output is correct
18	Correct	2666 ms	16472 KB	Output is correct
19	Correct	2669 ms	16472 KB	Output is correct
20	Correct	2226 ms	16472 KB	Output is correct
21	Correct	0 ms	2084 KB	Output is correct

Subtask #4
17.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	2084 KB	Output is correct
2	Correct	0 ms	2216 KB	Output is correct
3	Correct	0 ms	2216 KB	Output is correct
4	Correct	0 ms	2084 KB	Output is correct
5	Correct	0 ms	2084 KB	Output is correct
6	Correct	0 ms	2216 KB	Output is correct
7	Correct	0 ms	2084 KB	Output is correct
8	Correct	0 ms	2084 KB	Output is correct
9	Correct	0 ms	2216 KB	Output is correct
10	Correct	0 ms	2084 KB	Output is correct
11	Correct	0 ms	2084 KB	Output is correct
12	Correct	1169 ms	9608 KB	Output is correct
13	Correct	609 ms	9608 KB	Output is correct
14	Correct	1113 ms	9608 KB	Output is correct
15	Correct	1313 ms	9608 KB	Output is correct
16	Correct	733 ms	6308 KB	Output is correct
17	Correct	1256 ms	9740 KB	Output is correct
18	Correct	1018 ms	9608 KB	Output is correct
19	Correct	1939 ms	11324 KB	Output is correct
20	Correct	3039 ms	6440 KB	Output is correct
21	Correct	436 ms	2216 KB	Output is correct
22	Correct	3889 ms	8948 KB	Output is correct
23	Correct	293 ms	16472 KB	Output is correct
24	Correct	1693 ms	10268 KB	Output is correct
25	Correct	2699 ms	16472 KB	Output is correct
26	Correct	2169 ms	16472 KB	Output is correct
27	Correct	2143 ms	16472 KB	Output is correct
28	Correct	1296 ms	169196 KB	Output is correct
29	Correct	3399 ms	183716 KB	Output is correct
30	Correct	9193 ms	137384 KB	Output is correct
31	Correct	8893 ms	104912 KB	Output is correct
32	Correct	673 ms	2348 KB	Output is correct
33	Correct	1039 ms	4196 KB	Output is correct
34	Correct	656 ms	183584 KB	Output is correct
35	Correct	2983 ms	93428 KB	Output is correct
36	Correct	4326 ms	183716 KB	Output is correct
37	Correct	3916 ms	183716 KB	Output is correct
38	Correct	4553 ms	183716 KB	Output is correct
39	Correct	3123 ms	141080 KB	Output is correct
40	Correct	0 ms	2084 KB	Output is correct

Subtask #5
0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	2084 KB	Output is correct
2	Correct	0 ms	2216 KB	Output is correct
3	Correct	0 ms	2216 KB	Output is correct
4	Correct	0 ms	2084 KB	Output is correct
5	Correct	0 ms	2084 KB	Output is correct
6	Correct	0 ms	2216 KB	Output is correct
7	Correct	0 ms	2084 KB	Output is correct
8	Correct	0 ms	2084 KB	Output is correct
9	Correct	0 ms	2216 KB	Output is correct
10	Correct	0 ms	2084 KB	Output is correct
11	Correct	0 ms	2084 KB	Output is correct
12	Correct	1133 ms	9608 KB	Output is correct
13	Correct	749 ms	9608 KB	Output is correct
14	Correct	903 ms	9608 KB	Output is correct
15	Correct	1179 ms	9608 KB	Output is correct
16	Correct	769 ms	6308 KB	Output is correct
17	Correct	1146 ms	9740 KB	Output is correct
18	Correct	1069 ms	9608 KB	Output is correct
19	Correct	1853 ms	11324 KB	Output is correct
20	Correct	3176 ms	6440 KB	Output is correct
21	Correct	516 ms	2216 KB	Output is correct
22	Correct	3699 ms	8948 KB	Output is correct
23	Correct	263 ms	16472 KB	Output is correct
24	Correct	1676 ms	10268 KB	Output is correct
25	Correct	2593 ms	16472 KB	Output is correct
26	Correct	2733 ms	16472 KB	Output is correct
27	Correct	2516 ms	16472 KB	Output is correct
28	Correct	1363 ms	169196 KB	Output is correct
29	Correct	3236 ms	183716 KB	Output is correct
30	Correct	9299 ms	137384 KB	Output is correct
31	Correct	8423 ms	104912 KB	Output is correct
32	Correct	659 ms	2348 KB	Output is correct
33	Correct	1183 ms	4196 KB	Output is correct
34	Correct	629 ms	183584 KB	Output is correct
35	Correct	2249 ms	93428 KB	Output is correct
36	Correct	3873 ms	183716 KB	Output is correct
37	Correct	3176 ms	183716 KB	Output is correct
38	Correct	4276 ms	183716 KB	Output is correct
39	Memory limit exceeded	1269 ms	256000 KB	Memory limit exceeded
40	Halted	0 ms	0 KB	-

답안 #29171

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 27.0 / 27.0

Subtask #3 26.0 / 26.0

Subtask #4 17.0 / 17.0

Subtask #5 0 / 20.0

Subtask #1
10.0 / 10.0

Subtask #2
27.0 / 27.0

Subtask #3
26.0 / 26.0

Subtask #4
17.0 / 17.0

Subtask #5
0 / 20.0