oj.uz

Submission #18989

# Submission time Handle Problem Language Result Execution time Memory
18989 2016-02-17T02:25:07 Z suhgyuho_william Game (IOI13_game) C++
63 / 100
 2796 ms 256000 KB 
#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

# Verdict Execution time Memory 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 0 ms 1212 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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

# Verdict Execution time Memory 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 -