답안 #18989 :: oj.uz

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
18989	2016-02-17T02:25:07 Z	suhgyuho_william	게임 (IOI13_game)	C++	63 / 100	2796 ms	256000 KB

game

#include "game.h"
#include <stdio.h>
#include <stdlib.h>

#define lld long long

long long gcd2(long long X, long long Y) {
    long long tmp;

    if(X == 0) return Y;
    if(Y == 0) return X;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
struct datay{
    lld value;
    datay *left,*right;
    datay(){
        value = 0;
        left = right = NULL;
    }
};

struct datax{
    datax *left,*right;
    datay *yroot;
    datax(){
        left = right = NULL;
    }
}*xroot;

int R,C;
int nr,nc;

void init(int iR, int iC) {
    R = iR; C = iC;
    for(nr = 1; nr < R; nr *= 2);
    for(nc = 1; nc < C; nc *= 2);
    nr = R; nc = C;
    xroot = new datax();
    xroot -> yroot = new datay();
}

lld ans,value;
int findx,findy;
void yupdate1(datay *node,int left,int right){
    if(left == right){
        node -> value = value;
        return;
    }
    int mid = (left+right)/2;
    if(left <= findy && findy <= mid){
        if(node -> left == NULL) node -> left = new datay();
        yupdate1(node->left,left,mid);
    }
    if(mid+1 <= findy && findy <= right){
        if(node -> right == NULL) node -> right = new datay();
        yupdate1(node->right,mid+1,right);
    }
    if(node->left == NULL){
        if(node->right == NULL) node->value = 0;
        else node->value = (node->right)->value;
    }else{
        if(node->right == NULL) node->value = (node->left)->value;
        else node->value = gcd2((node->left)->value,(node->right)->value);
    }
}
void yclear(datay *node,int left,int right){
    node -> value = 0;
    if(left == right) return;
    int mid = (left+right)/2;
    if(left <= findy && findy <= mid){
        if(node -> left == NULL) node -> left = new datay();
        yclear(node->left,left,mid);
    }
    if(mid+1 <= findy && findy <= right){
        if(node -> right == NULL) node -> right = new datay();
        yclear(node->right,mid+1,right);
    }
}
void yupdate2(datay *node,datay *node2,int left,int right){
    node -> value = gcd2(node->value,node2->value);
    if(left == right) return;
    int mid = (left+right)/2;
    if(left <= findy && findy <= mid && node2->left != NULL) yupdate2(node->left,node2->left,left,mid);
    if(mid+1 <= findy && findy <= right && node2->right != NULL) yupdate2(node->right,node2->right,mid+1,right);
}
void xupdate(datax *node,int left,int right){
    if(node -> yroot == NULL) node -> yroot = new datay();
    if(left == right){
        yupdate1(node -> yroot,1,nc);
        return;
    }
    int mid = (left+right)/2;
    if(left <= findx && findx <= mid){
        if(node -> left == NULL) node -> left = new datax();
        xupdate(node->left,left,mid);
    }
    if(mid+1 <= findx && findx <= right){
        if(node -> right == NULL) node -> right = new datax();
        xupdate(node->right,mid+1,right);
    }
    yclear(node->yroot,1,nc);
    if(node -> left != NULL) yupdate2(node->yroot,(node->left)->yroot,1,nc);
    if(node ->right != NULL) yupdate2(node->yroot,(node->right)->yroot,1,nc);
}

void update(int iP, int iQ, long long K) {
    int P,Q;

    P = iP; Q = iQ;
    P++; Q++;
    findx = P;
    findy = Q;
    value = K;
    xupdate(xroot,1,nr);
}

int sx,ex,sy,ey;
bool crossy(int left,int right){
    if(ey < left || right < sy) return false;
    return true;
}
void ycalc(datay *node,int left,int right){
    if(sy <= left && right <= ey){
        ans = gcd2(ans,node->value);
        return;
    }
    int mid = (left+right)/2;
    if(crossy(left,mid) && node->left != NULL) ycalc(node->left,left,mid);
    if(crossy(mid+1,right) && node->right != NULL) ycalc(node->right,mid+1,right);
}
bool crossx(int left,int right){
    if(ex < left || right < sx) return false;
    return true;
}
void xcalc(datax *node,int left,int right){
    if(sx <= left && right <= ex){
        ycalc(node->yroot,1,nc);

        return;
    }
    int mid = (left+right)/2;
    if(crossx(left,mid) && node -> left != NULL) xcalc(node->left,left,mid);
    if(crossx(mid+1,right) && node -> right != NULL) xcalc(node->right,mid+1,right);
}

long long calculate(int iP, int iQ, int iU, int iV) {
    int P,Q,U,V;

    P = iP; Q = iQ; U = iU; V = iV;
    P++; Q++; U++; V++;
    ans = 0;
    sx = P; ex = U;
    sy = Q; ey = V;
    xcalc(xroot,1,nr);

    return ans;
}

Subtask #1
10.0 / 10.0

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

Subtask #2
27.0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1212 KB	Output is correct
2	Correct	0 ms	1212 KB	Output is correct
3	Correct	0 ms	1212 KB	Output is correct
4	Correct	843 ms	9396 KB	Output is correct
5	Correct	554 ms	9396 KB	Output is correct
6	Correct	582 ms	9660 KB	Output is correct
7	Correct	684 ms	9660 KB	Output is correct
8	Correct	467 ms	5964 KB	Output is correct
9	Correct	623 ms	9660 KB	Output is correct
10	Correct	527 ms	9660 KB	Output is correct
11	Correct	0 ms	1212 KB	Output is correct

Subtask #3
26.0 / 26.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1212 KB	Output is correct
2	Correct	0 ms	1212 KB	Output is correct
3	Correct	0 ms	1212 KB	Output is correct
4	Correct	0 ms	1212 KB	Output is correct
5	Correct	0 ms	1212 KB	Output is correct
6	Correct	0 ms	1212 KB	Output is correct
7	Correct	0 ms	1212 KB	Output is correct
8	Correct	0 ms	1212 KB	Output is correct
9	Correct	0 ms	1212 KB	Output is correct
10	Correct	0 ms	1212 KB	Output is correct
11	Correct	0 ms	1212 KB	Output is correct
12	Correct	1554 ms	12564 KB	Output is correct
13	Correct	2361 ms	6228 KB	Output is correct
14	Correct	304 ms	1212 KB	Output is correct
15	Correct	2788 ms	8868 KB	Output is correct
16	Correct	283 ms	18372 KB	Output is correct
17	Correct	944 ms	10980 KB	Output is correct
18	Correct	1537 ms	18372 KB	Output is correct
19	Correct	1347 ms	18372 KB	Output is correct
20	Correct	1171 ms	18372 KB	Output is correct
21	Correct	0 ms	1212 KB	Output is correct

Subtask #4
0.0 / 17.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1212 KB	Output is correct
2	Correct	0 ms	1212 KB	Output is correct
3	Correct	0 ms	1212 KB	Output is correct
4	Correct	0 ms	1212 KB	Output is correct
5	Correct	0 ms	1212 KB	Output is correct
6	Correct	0 ms	1212 KB	Output is correct
7	Correct	0 ms	1212 KB	Output is correct
8	Correct	0 ms	1212 KB	Output is correct
9	Correct	0 ms	1212 KB	Output is correct
10	Correct	0 ms	1212 KB	Output is correct
11	Correct	0 ms	1212 KB	Output is correct
12	Correct	821 ms	9396 KB	Output is correct
13	Correct	544 ms	9396 KB	Output is correct
14	Correct	571 ms	9660 KB	Output is correct
15	Correct	614 ms	9660 KB	Output is correct
16	Correct	427 ms	5964 KB	Output is correct
17	Correct	627 ms	9660 KB	Output is correct
18	Correct	525 ms	9660 KB	Output is correct
19	Correct	1578 ms	12564 KB	Output is correct
20	Correct	2433 ms	6228 KB	Output is correct
21	Correct	326 ms	1212 KB	Output is correct
22	Correct	2794 ms	8868 KB	Output is correct
23	Correct	309 ms	18372 KB	Output is correct
24	Correct	957 ms	10980 KB	Output is correct
25	Correct	1530 ms	18372 KB	Output is correct
26	Correct	1376 ms	18372 KB	Output is correct
27	Correct	1182 ms	18372 KB	Output is correct
28	Correct	1026 ms	251352 KB	Output is correct
29	Memory limit exceeded	2354 ms	256000 KB	Memory limit exceeded
30	Halted	0 ms	0 KB	-

Subtask #5
0.0 / 20.0

#	결과	실행 시간	메모리	Grader output
1	Correct	0 ms	1212 KB	Output is correct
2	Correct	1 ms	1212 KB	Output is correct
3	Correct	0 ms	1212 KB	Output is correct
4	Correct	0 ms	1212 KB	Output is correct
5	Correct	0 ms	1212 KB	Output is correct
6	Correct	0 ms	1212 KB	Output is correct
7	Correct	0 ms	1212 KB	Output is correct
8	Correct	0 ms	1212 KB	Output is correct
9	Correct	0 ms	1212 KB	Output is correct
10	Correct	0 ms	1212 KB	Output is correct
11	Correct	0 ms	1212 KB	Output is correct
12	Correct	824 ms	9396 KB	Output is correct
13	Correct	529 ms	9396 KB	Output is correct
14	Correct	587 ms	9660 KB	Output is correct
15	Correct	635 ms	9660 KB	Output is correct
16	Correct	431 ms	5964 KB	Output is correct
17	Correct	671 ms	9660 KB	Output is correct
18	Correct	511 ms	9660 KB	Output is correct
19	Correct	1567 ms	12564 KB	Output is correct
20	Correct	2353 ms	6228 KB	Output is correct
21	Correct	303 ms	1212 KB	Output is correct
22	Correct	2796 ms	8868 KB	Output is correct
23	Correct	320 ms	18372 KB	Output is correct
24	Correct	962 ms	10980 KB	Output is correct
25	Correct	1578 ms	18372 KB	Output is correct
26	Correct	1398 ms	18372 KB	Output is correct
27	Correct	1178 ms	18372 KB	Output is correct
28	Incorrect	1026 ms	251352 KB	Output isn't correct - wrong output format : File not found: "/var/www/temp/18989/output76z5_1"
29	Halted	0 ms	0 KB	-
30	Halted	0 ms	0 KB	-

답안 #18989

Compilation message

Subtask #1 10.0 / 10.0

Subtask #2 27.0 / 27.0

Subtask #3 26.0 / 26.0

Subtask #4 0.0 / 17.0

Subtask #5 0.0 / 20.0

Subtask #1
10.0 / 10.0

Subtask #2
27.0 / 27.0

Subtask #3
26.0 / 26.0

Subtask #4
0.0 / 17.0

Subtask #5
0.0 / 20.0