oj.uz

Submission #254582

# Submission time Handle Problem Language Result Execution time Memory
254582 2020-07-30T09:53:17 Z AaronNaidu Game (IOI13_game) C++14
37 / 100
 13000 ms 68968 KB 
#include <bits/stdc++.h>
#include "game.h"
using namespace std;
typedef long long ll;
ll bigNum = 1073741824;
ll mult = 1000000007;
ll r, c, p, q, u, v;
//ll segTree[32][262144];
unordered_map<ll, ll> segTree;
unordered_map<ll, ll> gcds;

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

long long gcd2(long long X, long long Y) {
    auto possAns = gcds.find({mult*X+Y});
    if (possAns != gcds.end())
    {
        return possAns->second;
    }
    long long tmp;
    while (X != Y && Y != 0) {
        tmp = X;
        X = Y;
        Y = tmp % Y;
    }
    gcds.insert({mult*X+Y, X});
    return X;
}

void update(int p, int q, ll k) {
    p += bigNum;
    q += bigNum;
    auto trash = segTree.find(mult * p + q);
    if (trash != segTree.end())
    {
        segTree.erase(trash);
    }
    
    segTree.insert({mult * 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(mult*2*pTemp + q);
            ll value1;
            if (place1 == segTree.end())
            {
                 value1 = 0;
            }
            else
            {
                value1 = place1->second;
            }

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

        auto place2 = segTree.find(mult*p + 2*q+1);
        ll value2;
        if (place2 == segTree.end())
        {
            value2 = 0;
        }
        else
        {
            value2 = place2->second;
        }
        trash = segTree.find(mult*p+ q);
        if (trash != segTree.end())
        {
            segTree.erase(trash);
        }
        
        segTree.insert({mult*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(mult*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 8 ms 384 KB Output is correct
2 Correct 24 ms 768 KB Output is correct
3 Correct 24 ms 768 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 20 ms 768 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 18 ms 768 KB Output is correct
10 Correct 7 ms 512 KB Output is correct
11 Correct 11 ms 512 KB Output is correct
12 Correct 1 ms 384 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 384 KB Output is correct
2 Correct 2 ms 308 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 6481 ms 68732 KB Output is correct
5 Correct 5312 ms 68468 KB Output is correct
6 Correct 6485 ms 67780 KB Output is correct
7 Correct 7691 ms 67096 KB Output is correct
8 Correct 4085 ms 41156 KB Output is correct
9 Correct 7281 ms 67648 KB Output is correct
10 Correct 7247 ms 66324 KB Output is correct
11 Correct 1 ms 384 KB Output is correct

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 384 KB Output is correct
2 Correct 20 ms 768 KB Output is correct
3 Correct 20 ms 768 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 20 ms 768 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 18 ms 744 KB Output is correct
10 Correct 7 ms 512 KB Output is correct
11 Correct 11 ms 512 KB Output is correct
12 Correct 11338 ms 33144 KB Output is correct
13 Correct 12782 ms 16132 KB Output is correct
14 Correct 5044 ms 5112 KB Output is correct
15 Execution timed out 13081 ms 20368 KB Time limit exceeded
16 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 384 KB Output is correct
2 Correct 20 ms 768 KB Output is correct
3 Correct 20 ms 768 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 20 ms 768 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 17 ms 768 KB Output is correct
10 Correct 7 ms 512 KB Output is correct
11 Correct 11 ms 512 KB Output is correct
12 Correct 7568 ms 68672 KB Output is correct
13 Correct 6153 ms 68692 KB Output is correct
14 Correct 8125 ms 67616 KB Output is correct
15 Correct 8480 ms 66904 KB Output is correct
16 Correct 4742 ms 41040 KB Output is correct
17 Correct 8103 ms 67384 KB Output is correct
18 Correct 6569 ms 66388 KB Output is correct
19 Correct 11120 ms 33152 KB Output is correct
20 Correct 12477 ms 16580 KB Output is correct
21 Correct 5038 ms 5948 KB Output is correct
22 Execution timed out 13024 ms 20768 KB Time limit exceeded
23 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 384 KB Output is correct
2 Correct 23 ms 768 KB Output is correct
3 Correct 22 ms 768 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 20 ms 768 KB Output is correct
7 Correct 2 ms 384 KB Output is correct
8 Correct 2 ms 384 KB Output is correct
9 Correct 18 ms 768 KB Output is correct
10 Correct 7 ms 512 KB Output is correct
11 Correct 11 ms 512 KB Output is correct
12 Correct 6906 ms 68776 KB Output is correct
13 Correct 5503 ms 68968 KB Output is correct
14 Correct 6771 ms 67484 KB Output is correct
15 Correct 6964 ms 66924 KB Output is correct
16 Correct 4069 ms 41152 KB Output is correct
17 Correct 7179 ms 67632 KB Output is correct
18 Correct 5977 ms 65696 KB Output is correct
19 Correct 10427 ms 33012 KB Output is correct
20 Correct 12190 ms 16432 KB Output is correct
21 Correct 4948 ms 5300 KB Output is correct
22 Execution timed out 13034 ms 20996 KB Time limit exceeded
23 Halted 0 ms 0 KB -