oj.uz

Submission #15777

# Submission time Handle Problem Language Result Execution time Memory
15777 2015-07-24T14:51:36 Z ainta Game (IOI13_game) C++
63 / 100
 3425 ms 256000 KB 
#include "game.h"
#include<stdio.h>
#include<algorithm>
using namespace std;

long long gcd2(long long X, long long Y) {
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}

struct SegY{
    long long G;
    SegY *c1, *c2;
    SegY(){
        G=0;
        c1=c2=NULL;
    }
};

struct SegX{
    long long G;
    SegX *c1, *c2;
    SegY *cy;
    SegX(){
        G=0;
        c1=c2=NULL;
        cy=NULL;
    }
};

SegX *rootX;
SegY *rootY;

int MR, MC;



void init(int R, int C) {
    rootX = new SegX();
    rootY = new SegY();
    MR = R, MC = C;
}

void InsY(SegY *nd, int b, int e, int y, long long K){
    if(b==e){
        nd->G = K;
        return;
    }
    int m = (b+e)>>1;
    if(!nd->c1){
        nd->c1 = new SegY();
        nd->c2 = new SegY();
    }
    if(y <= m)InsY(nd->c1, b, m, y, K);
    else InsY(nd->c2, m+1, e, y, K);
    nd->G = gcd2(nd->c1->G, nd->c2->G);
}

void UDT(SegY *nd, SegY *nd1, SegY *nd2, int b, int e, int y){
    nd->G = gcd2(nd1?nd1->G:0, nd2?nd2->G:0);
    if(b==e)return;
    int m = (b+e)>>1;
    if(!nd->c1)nd->c1 = new SegY(), nd->c2 = new SegY();
    if(y <= m)UDT(nd->c1, nd1?nd1->c1:NULL, nd2?nd2->c1:NULL, b, m, y);
    else UDT(nd->c2, nd1?nd1->c2:NULL, nd2?nd2->c2:NULL, m+1, e, y);
}

void InsX(SegX *nd, int b, int e, int x, int y, long long K){
    if(b==e){
        if(!nd->cy)nd->cy = new SegY();
        InsY(nd->cy, 0, MC - 1, y, K);
        return;
    }
    int m = (b+e)>>1;
    if(!nd->c1)nd->c1 = new SegX(), nd->c2 = new SegX();
    if(!nd->cy)nd->cy = new SegY();
    if(x <= m) InsX(nd->c1, b, m, x, y, K);
    else InsX(nd->c2, m+1, e, x, y, K);
    UDT(nd->cy, nd->c1->cy, nd->c2->cy, 0, MC - 1, y);
}

void update(int P, int Q, long long K) {
    InsX(rootX, 0, MR - 1, P, Q, K);
}

long long CalcY(SegY *nd, int b, int e, int s, int l){
    if(!nd)return 0;
    if(b == s && e == l)return nd->G;
    int m = (b+e)>>1;
    long long r = 0;
    if(s <= m && nd->c1) r = CalcY(nd->c1, b, m, s, min(m,l));
    if(l > m && nd->c2) r = gcd2(CalcY(nd->c2, m + 1, e, max(s, m+1), l), r);
    return r;
}

long long CalcX(SegX *nd, int b, int e, int s, int l, int by, int ey){
    if(b == s && e == l)return CalcY(nd->cy, 0, MC - 1, by, ey);
    int m = (b+e)>>1;
    long long r = 0;
    if(s <= m && nd->c1) r = CalcX(nd->c1, b, m, s, min(m,l), by, ey);
    if(l > m && nd->c2) r = gcd2(CalcX(nd->c2, m+1, e, max(m+1, s), l, by, ey), r);
    return r;
}

long long calculate(int P, int Q, int U, int V) {
    return CalcX(rootX, 0, MR - 1, P, U, Q, V);
}

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 1344 KB Output is correct
3 Correct 0 ms 1344 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 1344 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 1344 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 806 ms 15072 KB Output is correct
5 Correct 568 ms 15072 KB Output is correct
6 Correct 741 ms 15468 KB Output is correct
7 Correct 843 ms 15468 KB Output is correct
8 Correct 585 ms 9396 KB Output is correct
9 Correct 821 ms 15468 KB Output is correct
10 Correct 682 ms 15336 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 1344 KB Output is correct
3 Correct 1 ms 1344 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 1344 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 1344 KB Output is correct
10 Correct 0 ms 1212 KB Output is correct
11 Correct 1 ms 1212 KB Output is correct
12 Correct 1239 ms 19296 KB Output is correct
13 Correct 2828 ms 8736 KB Output is correct
14 Correct 402 ms 1344 KB Output is correct
15 Correct 3425 ms 13092 KB Output is correct
16 Correct 348 ms 29592 KB Output is correct
17 Correct 1431 ms 17844 KB Output is correct
18 Correct 2175 ms 29592 KB Output is correct
19 Correct 1943 ms 29592 KB Output is correct
20 Correct 1753 ms 29592 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 1344 KB Output is correct
3 Correct 0 ms 1344 KB Output is correct
4 Correct 0 ms 1212 KB Output is correct
5 Correct 1 ms 1212 KB Output is correct
6 Correct 0 ms 1344 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 1344 KB Output is correct
10 Correct 0 ms 1212 KB Output is correct
11 Correct 0 ms 1212 KB Output is correct
12 Correct 816 ms 15072 KB Output is correct
13 Correct 553 ms 15072 KB Output is correct
14 Correct 801 ms 15468 KB Output is correct
15 Correct 877 ms 15468 KB Output is correct
16 Correct 553 ms 9396 KB Output is correct
17 Correct 793 ms 15468 KB Output is correct
18 Correct 701 ms 15336 KB Output is correct
19 Correct 1271 ms 19296 KB Output is correct
20 Correct 2837 ms 8736 KB Output is correct
21 Correct 459 ms 1344 KB Output is correct
22 Correct 3354 ms 13092 KB Output is correct
23 Correct 310 ms 29592 KB Output is correct
24 Correct 1385 ms 17844 KB Output is correct
25 Correct 2254 ms 29592 KB Output is correct
26 Correct 1966 ms 29592 KB Output is correct
27 Correct 1804 ms 29592 KB Output is correct
28 Memory limit exceeded 662 ms 256000 KB Memory limit exceeded
29 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 0 ms 1344 KB Output is correct
3 Correct 0 ms 1344 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 1344 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 1344 KB Output is correct
10 Correct 0 ms 1212 KB Output is correct
11 Correct 1 ms 1212 KB Output is correct
12 Correct 858 ms 15072 KB Output is correct
13 Correct 548 ms 15072 KB Output is correct
14 Correct 783 ms 15468 KB Output is correct
15 Correct 880 ms 15468 KB Output is correct
16 Correct 538 ms 9396 KB Output is correct
17 Correct 827 ms 15468 KB Output is correct
18 Correct 750 ms 15336 KB Output is correct
19 Correct 1254 ms 19296 KB Output is correct
20 Correct 2979 ms 8736 KB Output is correct
21 Correct 450 ms 1344 KB Output is correct
22 Correct 3422 ms 13092 KB Output is correct
23 Correct 323 ms 29592 KB Output is correct
24 Correct 1640 ms 17844 KB Output is correct
25 Correct 2329 ms 29592 KB Output is correct
26 Correct 1971 ms 29592 KB Output is correct
27 Correct 2028 ms 29592 KB Output is correct
28 Memory limit exceeded 673 ms 256000 KB Memory limit exceeded
29 Halted 0 ms 0 KB -