oj.uz

Submission #254286

# Submission time Handle Problem Language Result Execution time Memory
254286 2020-07-29T17:46:38 Z AaronNaidu Game (IOI13_game) C++14
37 / 100
 13000 ms 96472 KB 
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
typedef long long ll;
ll bigNum = 1073741824;
ll r, c, p, q, u, v;
//ll segTree[32][262144];
map<pair<ll, ll>, ll> segTree;

void init(int R, int C) {
    r = R;
    c = C;
}

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;
}

void update(int p, int q, ll k) {
    p += bigNum;
    q += bigNum;
    auto trash = segTree.find({p, q});
    if (trash != segTree.end())
    {
        segTree.erase(trash);
    }
    
    segTree.insert({{p, q}, k});
    while (q > 0)
    {
        //cout << "Outerwhile q = " << q << "\n";
        ll pTemp = p/2;
        while (pTemp > 0)
        {
            //cout <<"Innerwhile p temp = " << pTemp << "\n";
            auto place1 = segTree.find({2*pTemp, q});
            ll value1;
            if (place1 == segTree.end())
            {
                 value1 = 0;
            }
            else
            {
                value1 = place1->second;
            }

            auto place2 = segTree.find({2*pTemp+1, q});
            ll value2;
            if (place2 == segTree.end())
            {
                 value2 = 0;
            }
            else
            {
                value2 = place2->second;
            }
            trash = segTree.find({pTemp, q});
            if (trash != segTree.end())
            {
                segTree.erase(trash);
            }
            
            segTree.insert({{pTemp, q}, gcd2(value1, value2)});
            pTemp /= 2;
        }
        q /= 2;
        auto place1 = segTree.find({p, 2*q});
        ll value1;
        if (place1 == segTree.end())
        {
            value1 = 0;
        }
        else
        {
            value1 = place1->second;
        }

        auto place2 = segTree.find({p, 2*q+1});
        ll value2;
        if (place2 == segTree.end())
        {
            value2 = 0;
        }
        else
        {
            value2 = place2->second;
        }
        trash = segTree.find({p, q});
        if (trash != segTree.end())
        {
            segTree.erase(trash);
        }
        
        segTree.insert({{p,q}, gcd2(value1, value2) }); 
        //cout << "End of outerwhile q = " << q << "\n";
    }

}

ll getSegTree(ll nodex, ll nodey, ll nodexstart, ll nodexend, ll nodeystart, ll nodeyend) {
    if (nodexstart > u or nodexend < p or nodeystart > v or nodeyend < q)
    {
        return 0;
    }
    if (nodexstart >= p and nodexend <= u)
    {
        if (nodeystart >= q and nodeyend <= v)
        {
            auto ansPlace = segTree.find({nodex, nodey});
            if (ansPlace == segTree.end())
            {
                return 0;
            }
            //cout << "Returning " << nodex << "," << nodey << " which is " << ansPlace->second;
            return ansPlace->second;
        }
        ll midy = (nodeystart + nodeyend)/2;
        return gcd2(getSegTree(nodex, 2*nodey, nodexstart, nodexend, nodeystart, midy), getSegTree(nodex, 2*nodey+1, nodexstart, nodexend, midy+1, nodeyend));
    }
    ll midx = (nodexstart + nodexend)/2;
    return gcd2(getSegTree(2*nodex, nodey, nodexstart, midx, nodeystart, nodeyend), getSegTree(2*nodex+1, nodey, midx + 1, nodexend, nodeystart, nodeyend));
}    
    
ll calculate(int P, int Q, int U, int V) {
    p = P;
    q = Q;
    u = U;
    v = V;
    return getSegTree(1, 1, 0, bigNum-1, 0, bigNum-1);
}

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 13 ms 384 KB Output is correct
2 Correct 35 ms 1016 KB Output is correct
3 Correct 37 ms 1016 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 41 ms 1016 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 30 ms 1016 KB Output is correct
10 Correct 11 ms 768 KB Output is correct
11 Correct 17 ms 604 KB Output is correct
12 Correct 2 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 8684 ms 96472 KB Output is correct
5 Correct 7099 ms 96392 KB Output is correct
6 Correct 8396 ms 93864 KB Output is correct
7 Correct 8534 ms 93552 KB Output is correct
8 Correct 4787 ms 56256 KB Output is correct
9 Correct 8696 ms 94100 KB Output is correct
10 Correct 8616 ms 93280 KB Output is correct
11 Correct 2 ms 384 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 384 KB Output is correct
2 Correct 35 ms 1016 KB Output is correct
3 Correct 35 ms 1016 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 34 ms 1016 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 30 ms 996 KB Output is correct
10 Correct 12 ms 768 KB Output is correct
11 Correct 17 ms 640 KB Output is correct
12 Correct 12377 ms 32736 KB Output is correct
13 Correct 12558 ms 20692 KB Output is correct
14 Correct 6599 ms 6420 KB Output is correct
15 Execution timed out 13049 ms 29228 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 384 KB Output is correct
2 Correct 42 ms 1016 KB Output is correct
3 Correct 35 ms 1016 KB Output is correct
4 Correct 4 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 37 ms 1024 KB Output is correct
7 Correct 3 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 31 ms 1052 KB Output is correct
10 Correct 12 ms 768 KB Output is correct
11 Correct 17 ms 640 KB Output is correct
12 Correct 8776 ms 95708 KB Output is correct
13 Correct 7161 ms 96300 KB Output is correct
14 Correct 8360 ms 93740 KB Output is correct
15 Correct 8453 ms 93416 KB Output is correct
16 Correct 4677 ms 56184 KB Output is correct
17 Correct 8690 ms 93936 KB Output is correct
18 Correct 8791 ms 93248 KB Output is correct
19 Correct 12299 ms 32936 KB Output is correct
20 Correct 12539 ms 17016 KB Output is correct
21 Correct 6503 ms 2068 KB Output is correct
22 Execution timed out 13100 ms 25720 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 384 KB Output is correct
2 Correct 36 ms 1016 KB Output is correct
3 Correct 35 ms 1056 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 34 ms 1020 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 29 ms 1016 KB Output is correct
10 Correct 12 ms 768 KB Output is correct
11 Correct 17 ms 640 KB Output is correct
12 Correct 8595 ms 95912 KB Output is correct
13 Correct 7209 ms 96336 KB Output is correct
14 Correct 8377 ms 93864 KB Output is correct
15 Correct 8767 ms 93384 KB Output is correct
16 Correct 4668 ms 56424 KB Output is correct
17 Correct 8545 ms 93924 KB Output is correct
18 Correct 8663 ms 92760 KB Output is correct
19 Correct 12424 ms 32560 KB Output is correct
20 Correct 12443 ms 20484 KB Output is correct
21 Correct 6559 ms 6136 KB Output is correct
22 Execution timed out 13087 ms 29292 KB Time limit exceeded
23 Halted 0 ms 0 KB -