oj.uz

Submission #7248

# Submission time Handle Problem Language Result Execution time Memory
7248 2014-07-28T13:16:37 Z Rhak Game (IOI13_game) C++
80 / 100
 9764 ms 256000 KB 
#include "game.h"
#include<stdio.h>
 
long long gcd2(long long x, long long y){ return y==0? x: gcd2(y, x%y); }
 
struct _node{
    _node *d[4];
    long long GCD;
    _node(long long GCD):GCD(GCD){ d[0] = d[1] = d[2] = d[3] = 0; }
};
 
struct _IndexTree{
    int S, E;
    _node *root;
    _IndexTree(int S,int E):S(S), E(E){ root = new _node(0);}
    void update(_node* n, int s, int e, int p, long long N, _IndexTree* l, _IndexTree* r)
    {
        if( p < s || e < p) return;
        else if( p == s && e == p){
            if( N != -1) n->GCD = N;
            else n->GCD = gcd2(l?l->read(s, e):0, r?r->read(s, e):0);
            return;
        }
        long long t[4] = {0}, fn = 0;
        for(int i = 0; i < 4; i++) t[i] = n->d[i]? n->d[i]->GCD:0;
        if( e >= s+4){
            for(long long i = 0; i < 4; i++){
                int ml = (( s*(4-i) + e*i) >> 2) + 1;
                int mr = ( s*(3-i) + e*(i+1)) >> 2;
                if(i == 0) ml--;
                if( ml <= p && p <= mr ){
                    if( !n->d[i] ) n->d[i] = new _node(0);
                    update(n->d[i], ml, mr, p, N, l, r);
                    t[i] = n->d[i]->GCD;
                }
            }
        }
        else{
            for(int j = s, i = 0; j <= e; i++, j++){
              if( j != p) continue;
                if( !n->d[i] ) n->d[i] = new _node(0);
                update(n->d[i], j, j, p, N, l, r);
                t[i] = n->d[i]->GCD;
            }
        }      
        for(int i = 0; i < 4; i ++) fn = gcd2(fn, t[i]);
        n->GCD = fn;
    }
    void update(int p, long long N)
    {
        update(root, S, E, p, N, 0, 0);
    }
 
    void update(int p, _IndexTree* l, _IndexTree* r)
    {
        update(root, S, E, p, -1, l, r);
    }
 
    long long read(_node *n, int s, int e, int p, int q)
    {
        if( !n ) return 0;
        if( q < s || e < p) return 0;
        else if( p <= s && e <= q){
            return n->GCD;
        }
        int m = (s+e) >> 1;
        long long t , fn = 0;
        if( e >= s+4){
            for(long long i = 0; i < 4; i++){
                int ml = (( s*(4-i) + e*i) >> 2) + 1;
                int mr = ( s*(3-i) + e*(i+1)) >> 2;
                if(i == 0) ml--;
                t = n->d[i]? read(n->d[i], ml, mr, p, q):0;
                fn = gcd2(fn, t);
            }
        }
        else{
            for(int j = s, i = 0; j <= e; i++, j++){
                t = n->d[i]? read(n->d[i], j, j, p, q):0;
                fn = gcd2(fn, t);
            }
        }      
        return fn;
    }
 
    long long read(int s,int e){
        return read(root, S, E, s, e);
    }
};
 
struct node{
    node *left, *right;
    _IndexTree *IT;
    node(int C){
        left = right = 0;
        IT = new _IndexTree(0, C-1);
    }
};
 
struct IndexTree{
    int S, E, C;
    node* root;
    IndexTree(int S, int E, int C):S(S), E(E), C(C){
        root = new node(C);
    }
     
    void update(node* n, int s, int e, int p, int q, long long N)
    {
        if( p < s || e < p) return;  
        if( p == s && e == p){
            n->IT->update(q, N);
            return;
        }
        int m = (s+e) >> 1;
        if( p <= m ){
            if( !n->left ) n->left = new node(C);
            update(n->left, s, m, p, q, N);
        }
        else{
            if( !n->right ) n->right = new node(C);
            update(n->right, m+1, e, p, q, N);
        }
        n->IT->update(q, n->left? n->left->IT : 0, n->right? n->right->IT : 0);
    }
    void update(int p, int q, long long N)
    {
        update(root, S, E, p, q, N);
    }
 
    long long read(node *n, int s, int e, int p, int q, int u, int v)
    {
        if( !n ) return 0;
        if( q < s || e < p) return 0;
        else if( p <= s && e <= q){
            return n->IT->read(u, v);
        }
        int m = (s+e) >> 1;
        long long t1 = n->left? read(n->left, s, m, p, q, u, v):0;
        long long t2 = n->right? read(n->right, m+1, e, p, q, u, v):0;
        return gcd2(t1, t2);
    }
    long long read(int P,int Q,int U, int V)
    {
        return read(root, S, E, P, Q, U, V);
    }
}*IT;
 
void init(int R, int C){
    IT = new IndexTree(0, R-1, C);
}
 
void update(int R, int C, long long K){
    IT->update(R, C, K);
}
 
long long calculate(int P, int Q, int U, int V){
    return IT->read(P, U, Q, V);
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1216 KB Output is correct
2 Correct 0 ms 1216 KB Output is correct
3 Correct 0 ms 1216 KB Output is correct
4 Correct 0 ms 1216 KB Output is correct
5 Correct 0 ms 1216 KB Output is correct
6 Correct 0 ms 1216 KB Output is correct
7 Correct 0 ms 1216 KB Output is correct
8 Correct 0 ms 1216 KB Output is correct
9 Correct 0 ms 1216 KB Output is correct
10 Correct 0 ms 1216 KB Output is correct
11 Correct 0 ms 1216 KB Output is correct
12 Correct 0 ms 1216 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1216 KB Output is correct
2 Correct 0 ms 1216 KB Output is correct
3 Correct 0 ms 1216 KB Output is correct
4 Correct 1228 ms 8608 KB Output is correct
5 Correct 900 ms 8608 KB Output is correct
6 Correct 1012 ms 8740 KB Output is correct
7 Correct 1140 ms 8740 KB Output is correct
8 Correct 708 ms 5308 KB Output is correct
9 Correct 1112 ms 8740 KB Output is correct
10 Correct 976 ms 8740 KB Output is correct
11 Correct 0 ms 1216 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1216 KB Output is correct
2 Correct 0 ms 1216 KB Output is correct
3 Correct 0 ms 1216 KB Output is correct
4 Correct 0 ms 1216 KB Output is correct
5 Correct 0 ms 1216 KB Output is correct
6 Correct 0 ms 1216 KB Output is correct
7 Correct 0 ms 1216 KB Output is correct
8 Correct 0 ms 1216 KB Output is correct
9 Correct 0 ms 1216 KB Output is correct
10 Correct 0 ms 1216 KB Output is correct
11 Correct 0 ms 1216 KB Output is correct
12 Correct 2148 ms 10852 KB Output is correct
13 Correct 3920 ms 5704 KB Output is correct
14 Correct 488 ms 1348 KB Output is correct
15 Correct 4520 ms 8872 KB Output is correct
16 Correct 436 ms 17452 KB Output is correct
17 Correct 1688 ms 10456 KB Output is correct
18 Correct 2804 ms 17452 KB Output is correct
19 Correct 2428 ms 17452 KB Output is correct
20 Correct 2224 ms 17452 KB Output is correct
21 Correct 0 ms 1216 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1216 KB Output is correct
2 Correct 0 ms 1216 KB Output is correct
3 Correct 0 ms 1216 KB Output is correct
4 Correct 0 ms 1216 KB Output is correct
5 Correct 0 ms 1216 KB Output is correct
6 Correct 0 ms 1216 KB Output is correct
7 Correct 0 ms 1216 KB Output is correct
8 Correct 0 ms 1216 KB Output is correct
9 Correct 0 ms 1216 KB Output is correct
10 Correct 0 ms 1216 KB Output is correct
11 Correct 0 ms 1216 KB Output is correct
12 Correct 1232 ms 8608 KB Output is correct
13 Correct 920 ms 8608 KB Output is correct
14 Correct 1036 ms 8740 KB Output is correct
15 Correct 1144 ms 8740 KB Output is correct
16 Correct 704 ms 5308 KB Output is correct
17 Correct 1120 ms 8740 KB Output is correct
18 Correct 1012 ms 8740 KB Output is correct
19 Correct 2116 ms 10852 KB Output is correct
20 Correct 3916 ms 5704 KB Output is correct
21 Correct 476 ms 1348 KB Output is correct
22 Correct 4524 ms 8872 KB Output is correct
23 Correct 408 ms 17452 KB Output is correct
24 Correct 1672 ms 10456 KB Output is correct
25 Correct 2756 ms 17452 KB Output is correct
26 Correct 2404 ms 17452 KB Output is correct
27 Correct 2256 ms 17452 KB Output is correct
28 Correct 1340 ms 201988 KB Output is correct
29 Correct 3596 ms 220072 KB Output is correct
30 Correct 9764 ms 161596 KB Output is correct
31 Correct 9124 ms 123316 KB Output is correct
32 Correct 968 ms 1480 KB Output is correct
33 Correct 1404 ms 3592 KB Output is correct
34 Correct 988 ms 219940 KB Output is correct
35 Correct 2320 ms 111304 KB Output is correct
36 Correct 4216 ms 220072 KB Output is correct
37 Correct 3560 ms 220072 KB Output is correct
38 Correct 3492 ms 220072 KB Output is correct
39 Correct 2984 ms 168856 KB Output is correct
40 Correct 0 ms 1216 KB Output is correct

Subtask #5
0.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 1216 KB Output is correct
2 Correct 0 ms 1216 KB Output is correct
3 Correct 0 ms 1216 KB Output is correct
4 Correct 0 ms 1216 KB Output is correct
5 Correct 0 ms 1216 KB Output is correct
6 Correct 0 ms 1216 KB Output is correct
7 Correct 0 ms 1216 KB Output is correct
8 Correct 0 ms 1216 KB Output is correct
9 Correct 0 ms 1216 KB Output is correct
10 Correct 0 ms 1216 KB Output is correct
11 Correct 0 ms 1216 KB Output is correct
12 Correct 1228 ms 8608 KB Output is correct
13 Correct 904 ms 8608 KB Output is correct
14 Correct 1012 ms 8740 KB Output is correct
15 Correct 1100 ms 8740 KB Output is correct
16 Correct 672 ms 5308 KB Output is correct
17 Correct 1080 ms 8740 KB Output is correct
18 Correct 956 ms 8740 KB Output is correct
19 Correct 2112 ms 10852 KB Output is correct
20 Correct 3864 ms 5704 KB Output is correct
21 Correct 472 ms 1348 KB Output is correct
22 Correct 4536 ms 8872 KB Output is correct
23 Correct 404 ms 17452 KB Output is correct
24 Correct 1672 ms 10456 KB Output is correct
25 Correct 2756 ms 17452 KB Output is correct
26 Correct 2400 ms 17452 KB Output is correct
27 Correct 2196 ms 17452 KB Output is correct
28 Correct 1388 ms 201988 KB Output is correct
29 Correct 3612 ms 220072 KB Output is correct
30 Correct 9656 ms 161596 KB Output is correct
31 Correct 9104 ms 123316 KB Output is correct
32 Correct 1016 ms 1480 KB Output is correct
33 Correct 1408 ms 3592 KB Output is correct
34 Correct 924 ms 219940 KB Output is correct
35 Correct 2328 ms 111304 KB Output is correct
36 Correct 4212 ms 220072 KB Output is correct
37 Correct 3512 ms 220072 KB Output is correct
38 Correct 3476 ms 220072 KB Output is correct
39 Memory limit exceeded 1156 ms 256000 KB Memory limit exceeded
40 Halted 0 ms 0 KB -