oj.uz

Submission #254281

# Submission time Handle Problem Language Result Execution time Memory
254281 2020-07-29T17:38:53 Z AaronNaidu Game (IOI13_game) C++14
37 / 100
 13000 ms 100084 KB 
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
typedef long long ll;

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 += pow(2, 30);
    q += pow(2, 30);
    if (segTree.find({p, q}) != segTree.end())
    {
        segTree.erase(segTree.find({p, q}));
    }
    
    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;
            }
            if (segTree.find({pTemp, q}) != segTree.end())
            {
                segTree.erase(segTree.find({pTemp, q}));
            }
            
            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;
        }
        if (segTree.find({p, q}) != segTree.end())
        {
            segTree.erase(segTree.find({p, q}));
        }
        
        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, pow(2, 30)-1, 0, pow(2, 30)-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 15 ms 384 KB Output is correct
2 Correct 40 ms 1024 KB Output is correct
3 Correct 41 ms 1016 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 39 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 34 ms 1016 KB Output is correct
10 Correct 13 ms 768 KB Output is correct
11 Correct 19 ms 640 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 21 ms 440 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 9199 ms 96880 KB Output is correct
5 Correct 7919 ms 96504 KB Output is correct
6 Correct 9187 ms 94124 KB Output is correct
7 Correct 10200 ms 93664 KB Output is correct
8 Correct 5320 ms 56440 KB Output is correct
9 Correct 9930 ms 94148 KB Output is correct
10 Correct 10125 ms 93560 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 41 ms 968 KB Output is correct
3 Correct 40 ms 1024 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 39 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 34 ms 1016 KB Output is correct
10 Correct 13 ms 768 KB Output is correct
11 Correct 20 ms 656 KB Output is correct
12 Execution timed out 13061 ms 36504 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 384 KB Output is correct
2 Correct 45 ms 1024 KB Output is correct
3 Correct 41 ms 1024 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 40 ms 1144 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 35 ms 1016 KB Output is correct
10 Correct 13 ms 768 KB Output is correct
11 Correct 20 ms 632 KB Output is correct
12 Correct 9138 ms 99940 KB Output is correct
13 Correct 7783 ms 99940 KB Output is correct
14 Correct 9018 ms 97784 KB Output is correct
15 Correct 9021 ms 97516 KB Output is correct
16 Correct 5040 ms 59896 KB Output is correct
17 Correct 9149 ms 97992 KB Output is correct
18 Correct 8956 ms 97540 KB Output is correct
19 Correct 12807 ms 36484 KB Output is correct
20 Correct 12929 ms 20360 KB Output is correct
21 Correct 7151 ms 6244 KB Output is correct
22 Execution timed out 13096 ms 28964 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 384 KB Output is correct
2 Correct 40 ms 1024 KB Output is correct
3 Correct 40 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 39 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 34 ms 1020 KB Output is correct
10 Correct 13 ms 768 KB Output is correct
11 Correct 20 ms 640 KB Output is correct
12 Correct 9130 ms 99992 KB Output is correct
13 Correct 7722 ms 100084 KB Output is correct
14 Correct 9104 ms 98128 KB Output is correct
15 Correct 8950 ms 97648 KB Output is correct
16 Correct 4847 ms 60068 KB Output is correct
17 Correct 9115 ms 98188 KB Output is correct
18 Correct 9646 ms 97660 KB Output is correct
19 Execution timed out 13059 ms 36552 KB Time limit exceeded
20 Halted 0 ms 0 KB -