oj.uz

Submission #54191

# Submission time Handle Problem Language Result Execution time Memory
54191 2018-07-02T17:19:56 Z KieranHorgan Game (IOI13_game) C++17
37 / 100
 13000 ms 65976 KB 
#pragma GCC optimize("Ofast")
#include "game.h"
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define ll long long
 
long long gcd2(long long X, long long Y) {
    long long tmp;
    if(X==0&&Y==0) return 0;
    if(X==0) return Y;
    if(Y==0) return X;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    return X;
}
 
int R, C;

struct colSegmentTree {
    unordered_map<ll, ll> st;
    void update(ll val, int j, colSegmentTree *leftChild=NULL, colSegmentTree *rightChild=NULL, ll id=1, int l=0, int r=C) {
        if(l>j || r<=j) return;
        if(r-l==1) {
            if(leftChild==NULL&&rightChild==NULL) st[id] = val;
            else if(leftChild==NULL) st[id] = rightChild->st[id];
            else if(rightChild==NULL) st[id] = leftChild->st[id];
            else st[id] = gcd2(leftChild->st[id], rightChild->st[id]);
            return;
        }
        int mid = (l+r)/2;
        if(j < mid) update(val, j, leftChild, rightChild, id*2  , l, mid);
        else        update(val, j, leftChild, rightChild, id*2+1, mid, r);
        if(st.count(id*2  )&&
           st.count(id*2+1))
            st[id] = gcd2(st[id*2], st[id*2+1]);
        else if(st.count(id*2  ))
            st[id] = st[id*2  ];
        else if(st.count(id*2+1))
            st[id] = st[id*2+1];
    }
    ll query(int x, int y, ll id=1, int l=0, int r=C) {
        if(l>=y || r<=x) return 0;
        if(!st.count(id)) return 0;
        if(l>=x && r<=y) {
            // cerr << " " << l << " " << r-1 << endl;
            return st[id];
        }
        int mid = (l+r)/2;
        return gcd2(query(x, y, id*2  , l, mid),
                    query(x, y, id*2+1, mid, r));
    }
};

struct rowSegmentTree {
    unordered_map<ll, colSegmentTree> st;
    void update(ll val, int i, int j, ll id=1, int l=0, int r=R) {
        if(l+1==r) {
            // leftChild = NULL; rightChild = NULL;
            st[id].update(val, j);
            return;
        }
        int mid = (l+r)/2;
        if(i < mid) update(val, i, j, id*2  , l, mid);
        else        update(val, i, j, id*2+1, mid, r);
        // leftChild = &st[id*2  ];
        // rightChild = &st[id*2+1];
        if(!st.count(id*2)&&!st.count(id*2+1)) st[id].update(val, j, NULL, NULL);
        else if(!st.count(id*2)) st[id].update(val, j, NULL, &st[id*2+1]);
        else if(!st.count(id*2+1)) st[id].update(val, j, &st[id*2], NULL);
        else st[id].update(val, j, &st[id*2], &st[id*2+1]);
    }
    ll query(int x, int y, int nx, int ny, ll id=1, int l=0, int r=R) {
        if(l>=y || r<=x) return 0;
        if(!st.count(id)) return 0;
        if(l>=x && r<=y) {
            // cerr << l << " " << r-1 << endl;
            return st[id].query(nx, ny);
        }
        int mid = (l+r)/2;
        return gcd2(query(x, y, nx, ny, id*2  , l, mid),
                    query(x, y, nx, ny, id*2+1, mid, r));
    }
};
 
rowSegmentTree tree;
 
void init(signed r, signed c) {
    R = 1000000000;
    C = 1000000000;
//    for(int i = 0; i < R; i++)
//        for(int j = 0; j < C; j++)
//            update(i,j,rand());
    /* ... */
}
 
void update(signed P, signed Q, long long K) {
    tree.update(K, P, Q);
    /* ... */
}
 
long long calculate(signed P, signed Q, signed U, signed V) {
    /* ... */
    return tree.query(P, U+1, Q, V+1);
}
 
void test() {
//    for(int P = 0; P < 1000000000; P++)
//        for(int Q = 0; Q < 1000000000; Q++)
//            for(int U = P; U < 1000000000; U++)
//                for(int V = Q; V < 1000000000; V++)
//                    cerr << tree.query(P, U+1, Q, V+1) << endl;
}

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

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

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 948 KB Output is correct
2 Correct 3 ms 948 KB Output is correct
3 Correct 3 ms 948 KB Output is correct
4 Correct 6990 ms 65732 KB Output is correct
5 Correct 5418 ms 65976 KB Output is correct
6 Correct 6485 ms 65976 KB Output is correct
7 Correct 6490 ms 65976 KB Output is correct
8 Correct 3968 ms 65976 KB Output is correct
9 Correct 7046 ms 65976 KB Output is correct
10 Correct 6336 ms 65976 KB Output is correct
11 Correct 2 ms 65976 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 65976 KB Output is correct
2 Correct 14 ms 65976 KB Output is correct
3 Correct 14 ms 65976 KB Output is correct
4 Correct 3 ms 65976 KB Output is correct
5 Correct 2 ms 65976 KB Output is correct
6 Correct 13 ms 65976 KB Output is correct
7 Correct 2 ms 65976 KB Output is correct
8 Correct 3 ms 65976 KB Output is correct
9 Correct 12 ms 65976 KB Output is correct
10 Correct 6 ms 65976 KB Output is correct
11 Correct 7 ms 65976 KB Output is correct
12 Correct 9829 ms 65976 KB Output is correct
13 Correct 12355 ms 65976 KB Output is correct
14 Correct 2805 ms 65976 KB Output is correct
15 Execution timed out 13086 ms 65976 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 65976 KB Output is correct
2 Correct 15 ms 65976 KB Output is correct
3 Correct 14 ms 65976 KB Output is correct
4 Correct 3 ms 65976 KB Output is correct
5 Correct 2 ms 65976 KB Output is correct
6 Correct 13 ms 65976 KB Output is correct
7 Correct 3 ms 65976 KB Output is correct
8 Correct 3 ms 65976 KB Output is correct
9 Correct 12 ms 65976 KB Output is correct
10 Correct 6 ms 65976 KB Output is correct
11 Correct 8 ms 65976 KB Output is correct
12 Correct 6923 ms 65976 KB Output is correct
13 Correct 5443 ms 65976 KB Output is correct
14 Correct 6453 ms 65976 KB Output is correct
15 Correct 6453 ms 65976 KB Output is correct
16 Correct 3724 ms 65976 KB Output is correct
17 Correct 7035 ms 65976 KB Output is correct
18 Correct 7420 ms 65976 KB Output is correct
19 Correct 9953 ms 65976 KB Output is correct
20 Correct 12177 ms 65976 KB Output is correct
21 Correct 2986 ms 65976 KB Output is correct
22 Execution timed out 13103 ms 65976 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 65976 KB Output is correct
2 Correct 21 ms 65976 KB Output is correct
3 Correct 14 ms 65976 KB Output is correct
4 Correct 4 ms 65976 KB Output is correct
5 Correct 2 ms 65976 KB Output is correct
6 Correct 14 ms 65976 KB Output is correct
7 Correct 3 ms 65976 KB Output is correct
8 Correct 3 ms 65976 KB Output is correct
9 Correct 15 ms 65976 KB Output is correct
10 Correct 6 ms 65976 KB Output is correct
11 Correct 8 ms 65976 KB Output is correct
12 Correct 7688 ms 65976 KB Output is correct
13 Correct 6372 ms 65976 KB Output is correct
14 Correct 7080 ms 65976 KB Output is correct
15 Correct 7024 ms 65976 KB Output is correct
16 Correct 3717 ms 65976 KB Output is correct
17 Correct 6749 ms 65976 KB Output is correct
18 Correct 7495 ms 65976 KB Output is correct
19 Correct 10801 ms 65976 KB Output is correct
20 Correct 12904 ms 65976 KB Output is correct
21 Correct 2816 ms 65976 KB Output is correct
22 Execution timed out 13058 ms 65976 KB Time limit exceeded
23 Halted 0 ms 0 KB -