답안 #29168 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
29168	2017-07-18T13:28:50 Z	nibnalin	게임 (IOI13_game)	C++14	80 / 100	9883 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{
    long long val;
    node *ychild;
    nodex *left , *beech , *right;
    nodex(){
        val = 0LL;
        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	1159 ms	9608 KB	Output is correct
5	Correct	723 ms	9608 KB	Output is correct
6	Correct	1109 ms	9608 KB	Output is correct
7	Correct	1139 ms	9608 KB	Output is correct
8	Correct	719 ms	6308 KB	Output is correct
9	Correct	1236 ms	9740 KB	Output is correct
10	Correct	1099 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	1889 ms	11324 KB	Output is correct
13	Correct	3463 ms	6440 KB	Output is correct
14	Correct	439 ms	2216 KB	Output is correct
15	Correct	3749 ms	8948 KB	Output is correct
16	Correct	226 ms	16472 KB	Output is correct
17	Correct	1983 ms	10268 KB	Output is correct
18	Correct	3186 ms	16472 KB	Output is correct
19	Correct	2773 ms	16472 KB	Output is correct
20	Correct	2756 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	1113 ms	9608 KB	Output is correct
13	Correct	643 ms	9608 KB	Output is correct
14	Correct	1056 ms	9608 KB	Output is correct
15	Correct	1133 ms	9608 KB	Output is correct
16	Correct	726 ms	6308 KB	Output is correct
17	Correct	1099 ms	9740 KB	Output is correct
18	Correct	999 ms	9608 KB	Output is correct
19	Correct	1946 ms	11324 KB	Output is correct
20	Correct	3296 ms	6440 KB	Output is correct
21	Correct	419 ms	2216 KB	Output is correct
22	Correct	3686 ms	8948 KB	Output is correct
23	Correct	236 ms	16472 KB	Output is correct
24	Correct	1879 ms	10268 KB	Output is correct
25	Correct	3059 ms	16472 KB	Output is correct
26	Correct	2789 ms	16472 KB	Output is correct
27	Correct	2353 ms	16472 KB	Output is correct
28	Correct	1189 ms	169196 KB	Output is correct
29	Correct	3136 ms	183716 KB	Output is correct
30	Correct	9883 ms	137384 KB	Output is correct
31	Correct	8906 ms	104912 KB	Output is correct
32	Correct	706 ms	2348 KB	Output is correct
33	Correct	1119 ms	4196 KB	Output is correct
34	Correct	566 ms	183584 KB	Output is correct
35	Correct	2349 ms	93428 KB	Output is correct
36	Correct	4543 ms	183716 KB	Output is correct
37	Correct	3796 ms	183716 KB	Output is correct
38	Correct	3686 ms	183716 KB	Output is correct
39	Correct	3296 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	1066 ms	9608 KB	Output is correct
13	Correct	606 ms	9608 KB	Output is correct
14	Correct	1059 ms	9608 KB	Output is correct
15	Correct	1006 ms	9608 KB	Output is correct
16	Correct	643 ms	6308 KB	Output is correct
17	Correct	1136 ms	9740 KB	Output is correct
18	Correct	1069 ms	9608 KB	Output is correct
19	Correct	1726 ms	11324 KB	Output is correct
20	Correct	3319 ms	6440 KB	Output is correct
21	Correct	493 ms	2216 KB	Output is correct
22	Correct	4053 ms	8948 KB	Output is correct
23	Correct	226 ms	16472 KB	Output is correct
24	Correct	1796 ms	10268 KB	Output is correct
25	Correct	3173 ms	16472 KB	Output is correct
26	Correct	2793 ms	16472 KB	Output is correct
27	Correct	2566 ms	16472 KB	Output is correct
28	Correct	1089 ms	169196 KB	Output is correct
29	Correct	3083 ms	183716 KB	Output is correct
30	Correct	9266 ms	137384 KB	Output is correct
31	Correct	8903 ms	104912 KB	Output is correct
32	Correct	736 ms	2348 KB	Output is correct
33	Correct	1159 ms	4196 KB	Output is correct
34	Correct	663 ms	183584 KB	Output is correct
35	Correct	2923 ms	93428 KB	Output is correct
36	Correct	4509 ms	183716 KB	Output is correct
37	Correct	4289 ms	183716 KB	Output is correct
38	Correct	3653 ms	183716 KB	Output is correct
39	Memory limit exceeded	889 ms	256000 KB	Memory limit exceeded
40	Halted	0 ms	0 KB	-

답안 #29168

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