oj.uz

Submission #254287

# Submission time Handle Problem Language Result Execution time Memory
254287 2020-07-29T17:54:15 Z AaronNaidu Game (IOI13_game) C++14
63 / 100
 13000 ms 106060 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;

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(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 7 ms 384 KB Output is correct
2 Correct 19 ms 768 KB Output is correct
3 Correct 17 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 16 ms 768 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 15 ms 768 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 9 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 7 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 5260 ms 64352 KB Output is correct
5 Correct 4126 ms 64616 KB Output is correct
6 Correct 4888 ms 61904 KB Output is correct
7 Correct 4724 ms 61464 KB Output is correct
8 Correct 2943 ms 36076 KB Output is correct
9 Correct 4728 ms 61580 KB Output is correct
10 Correct 4657 ms 61136 KB Output is correct
11 Correct 1 ms 384 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 384 KB Output is correct
2 Correct 19 ms 768 KB Output is correct
3 Correct 18 ms 768 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 17 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 15 ms 768 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 9 ms 512 KB Output is correct
12 Correct 6174 ms 28944 KB Output is correct
13 Correct 5576 ms 12452 KB Output is correct
14 Correct 3689 ms 1528 KB Output is correct
15 Correct 6804 ms 17112 KB Output is correct
16 Correct 3408 ms 34384 KB Output is correct
17 Correct 4952 ms 31012 KB Output is correct
18 Correct 7555 ms 35736 KB Output is correct
19 Correct 7147 ms 35944 KB Output is correct
20 Correct 6795 ms 35304 KB Output is correct
21 Correct 1 ms 384 KB Output is correct

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 384 KB Output is correct
2 Correct 20 ms 768 KB Output is correct
3 Correct 18 ms 896 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 17 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 15 ms 720 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 9 ms 512 KB Output is correct
12 Correct 4977 ms 64432 KB Output is correct
13 Correct 4129 ms 64728 KB Output is correct
14 Correct 4861 ms 61948 KB Output is correct
15 Correct 4773 ms 61440 KB Output is correct
16 Correct 3112 ms 36176 KB Output is correct
17 Correct 4855 ms 61652 KB Output is correct
18 Correct 4610 ms 61320 KB Output is correct
19 Correct 6238 ms 29068 KB Output is correct
20 Correct 5627 ms 12680 KB Output is correct
21 Correct 3677 ms 1432 KB Output is correct
22 Correct 7029 ms 17372 KB Output is correct
23 Correct 3308 ms 34488 KB Output is correct
24 Correct 4946 ms 31188 KB Output is correct
25 Correct 7254 ms 35676 KB Output is correct
26 Correct 6931 ms 36056 KB Output is correct
27 Correct 6807 ms 35384 KB Output is correct
28 Execution timed out 13088 ms 106060 KB Time limit exceeded
29 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 384 KB Output is correct
2 Correct 17 ms 768 KB Output is correct
3 Correct 17 ms 768 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Correct 1 ms 256 KB Output is correct
6 Correct 17 ms 768 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 15 ms 768 KB Output is correct
10 Correct 6 ms 512 KB Output is correct
11 Correct 9 ms 512 KB Output is correct
12 Correct 5027 ms 64352 KB Output is correct
13 Correct 4203 ms 64656 KB Output is correct
14 Correct 4605 ms 61784 KB Output is correct
15 Correct 4863 ms 61376 KB Output is correct
16 Correct 2724 ms 35888 KB Output is correct
17 Correct 5148 ms 61724 KB Output is correct
18 Correct 4642 ms 61176 KB Output is correct
19 Correct 5941 ms 28852 KB Output is correct
20 Correct 5600 ms 12348 KB Output is correct
21 Correct 3685 ms 1276 KB Output is correct
22 Correct 6790 ms 17028 KB Output is correct
23 Correct 3301 ms 34284 KB Output is correct
24 Correct 4856 ms 31008 KB Output is correct
25 Correct 7227 ms 35720 KB Output is correct
26 Correct 7292 ms 35844 KB Output is correct
27 Correct 6725 ms 35176 KB Output is correct
28 Execution timed out 13024 ms 104056 KB Time limit exceeded
29 Halted 0 ms 0 KB -