oj.uz

Submission #281796

# Submission time Handle Problem Language Result Execution time Memory
281796 2020-08-23T13:29:26 Z Kastanda Game (IOI13_game) C++14
100 / 100
 5172 ms 62496 KB 
// M
#include<bits/stdc++.h>
#include "game.h"
#define lc (id << 1)
#define rc (lc ^ 1)
#define md ((l + r) >> 1)
using namespace std;
typedef long long ll;
const int N = 22005 * 4, TF = 400, MXS = N * 4, NS = N * 15;
int n, m, k, segk;
map < pair < int , int > , ll > MP, TMp;
vector < pair < int , int > > V[N], VC[MXS];
vector < int > UX, VID[MXS];
ll G[NS * 2];
inline void ModifySeg(int i, ll val)
{
        G[i += NS] = val;
        for (; i; i >>= 1)
                G[i >> 1] = __gcd(G[i], G[i ^ 1]);
}
inline ll GetSeg(int l, int r)
{
        ll g = 0;
        for (l += NS, r += NS; l < r; l >>= 1, r >>= 1)
        {
                if (l & 1) g = __gcd(g, G[l ++]);
                if (r & 1) g = __gcd(g, G[-- r]);
        }
        return g;
}
void Build(int id = 1, int l = 0, int r = k)
{
        VC[id].clear();
        VID[id].clear();
        if (r - l < 2)
                sort(V[l].begin(), V[l].end()), VC[id] = V[l];
        else
        {
                Build(lc, l, md);
                Build(rc, md, r);
                merge(VC[lc].begin(), VC[lc].end(), VC[rc].begin(), VC[rc].end(), back_inserter(VC[id]));
        }
        for (int i = 0; i < (int)VC[id].size(); i ++)
        {
                ModifySeg(segk, MP[make_pair(VC[id][i].second, VC[id][i].first)]);
                VID[id].push_back(segk ++);
        }
}
inline void Relax()
{
        segk = 0;
        memset(G, 0, sizeof(G));
        UX.clear();
        for (auto X : TMp)
                MP[X.first] = X.second;
        TMp.clear();

        for (auto e : MP)
                UX.push_back(e.first.first);
        UX.resize(unique(UX.begin(), UX.end()) - UX.begin());
        k = (int)UX.size();
        for (int i = 0; i <= k; i ++)
                V[i].clear();

        int ptr = 0;
        for (auto e : MP)
        {
                while (UX[ptr] < e.first.first)
                        ptr ++;
                V[ptr].push_back(make_pair(e.first.second, e.first.first));
        }
        Build();
        assert(segk < NS);
}
void Update(int i, int c, ll val, int id = 1, int l = 0, int r = k)
{
        int lb = (int)(lower_bound(VC[id].begin(), VC[id].end(), make_pair(c, UX[i])) - VC[id].begin());
        ModifySeg(VID[id][lb], val);
        if (r - l < 2)
                return ;
        if (i < md)
                Update(i, c, val, lc, l, md);
        else
                Update(i, c, val, rc, md, r);
}
void init(int _n, int _m)
{
        n = _n; m = _m;
        Relax();
}
void update(int r, int c, ll val)
{
        if (MP.count({r, c}))
        {
                r = lower_bound(UX.begin(), UX.end(), r) - UX.begin();
                Update(r, c, val);
                MP[make_pair(UX[r], c)] = val;
        }
        else
        {
                TMp[make_pair(r, c)] = val;
                if ((int)TMp.size() >= TF)
                        Relax();
        }
}
ll Get(int le, int ri, int lq, int rq, int id = 1, int l = 0, int r = k)
{
        if (ri <= l || r <= le)
                return 0LL;
        if (le <= l && r <= ri)
        {
                int lb = (int)(lower_bound(VC[id].begin(), VC[id].end(), make_pair(lq, -1)) - VC[id].begin());
                int ub = (int)(lower_bound(VC[id].begin(), VC[id].end(), make_pair(rq, -1)) - VC[id].begin());
                if (lb < ub)
                        return GetSeg(VID[id][lb], VID[id][ub - 1] + 1);
                return 0;
        }
        return __gcd(Get(le, ri, lq, rq, lc, l, md), Get(le, ri, lq, rq, rc, md, r));
}
inline ll Query(int a, int b, int c, int d)
{
        c ++; d ++;
        a = lower_bound(UX.begin(), UX.end(), a) - UX.begin();
        c = lower_bound(UX.begin(), UX.end(), c) - UX.begin();
        return Get(a, c, b, d);
}
ll calculate(int a, int b, int c, int d)
{
        ll g = Query(a, b, c, d);
        for (auto e : TMp)
                if (e.first.first >= a && e.first.first <= c && e.first.second >= b && e.first.second <= d)
                        g = __gcd(g, e.second);
        return g;
}

Compilation message

grader.c: In function 'int main()':
grader.c:18:6: warning: variable 'res' set but not used [-Wunused-but-set-variable]
   18 |  int res;
      |      ^~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 39552 KB Output is correct
2 Correct 23 ms 39552 KB Output is correct
3 Correct 23 ms 39552 KB Output is correct
4 Correct 23 ms 39584 KB Output is correct
5 Correct 23 ms 39672 KB Output is correct
6 Correct 23 ms 39680 KB Output is correct
7 Correct 27 ms 39544 KB Output is correct
8 Correct 23 ms 39552 KB Output is correct
9 Correct 23 ms 39552 KB Output is correct
10 Correct 23 ms 39552 KB Output is correct
11 Correct 23 ms 39552 KB Output is correct
12 Correct 23 ms 39552 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 39552 KB Output is correct
2 Correct 24 ms 39540 KB Output is correct
3 Correct 23 ms 39544 KB Output is correct
4 Correct 1296 ms 46328 KB Output is correct
5 Correct 1090 ms 46476 KB Output is correct
6 Correct 1339 ms 42888 KB Output is correct
7 Correct 1499 ms 42756 KB Output is correct
8 Correct 817 ms 42764 KB Output is correct
9 Correct 1416 ms 42864 KB Output is correct
10 Correct 1424 ms 42340 KB Output is correct
11 Correct 23 ms 39672 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 39552 KB Output is correct
2 Correct 24 ms 39552 KB Output is correct
3 Correct 26 ms 39544 KB Output is correct
4 Correct 24 ms 39552 KB Output is correct
5 Correct 23 ms 39552 KB Output is correct
6 Correct 24 ms 39552 KB Output is correct
7 Correct 27 ms 39680 KB Output is correct
8 Correct 24 ms 39552 KB Output is correct
9 Correct 24 ms 39552 KB Output is correct
10 Correct 24 ms 39552 KB Output is correct
11 Correct 24 ms 39552 KB Output is correct
12 Correct 1846 ms 47396 KB Output is correct
13 Correct 2492 ms 43260 KB Output is correct
14 Correct 1185 ms 41100 KB Output is correct
15 Correct 2536 ms 43360 KB Output is correct
16 Correct 787 ms 44392 KB Output is correct
17 Correct 1226 ms 43392 KB Output is correct
18 Correct 2586 ms 44616 KB Output is correct
19 Correct 1959 ms 44852 KB Output is correct
20 Correct 1923 ms 44192 KB Output is correct
21 Correct 25 ms 39552 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 39544 KB Output is correct
2 Correct 26 ms 39552 KB Output is correct
3 Correct 24 ms 39552 KB Output is correct
4 Correct 26 ms 39552 KB Output is correct
5 Correct 23 ms 39552 KB Output is correct
6 Correct 24 ms 39552 KB Output is correct
7 Correct 25 ms 39552 KB Output is correct
8 Correct 23 ms 39552 KB Output is correct
9 Correct 26 ms 39552 KB Output is correct
10 Correct 23 ms 39544 KB Output is correct
11 Correct 24 ms 39552 KB Output is correct
12 Correct 1274 ms 46296 KB Output is correct
13 Correct 1022 ms 46556 KB Output is correct
14 Correct 1081 ms 42976 KB Output is correct
15 Correct 1542 ms 42628 KB Output is correct
16 Correct 806 ms 42872 KB Output is correct
17 Correct 1404 ms 42664 KB Output is correct
18 Correct 1444 ms 42356 KB Output is correct
19 Correct 1833 ms 47240 KB Output is correct
20 Correct 2508 ms 43224 KB Output is correct
21 Correct 1171 ms 40952 KB Output is correct
22 Correct 2595 ms 43388 KB Output is correct
23 Correct 756 ms 44280 KB Output is correct
24 Correct 1256 ms 43304 KB Output is correct
25 Correct 2528 ms 44664 KB Output is correct
26 Correct 1951 ms 44716 KB Output is correct
27 Correct 1947 ms 43412 KB Output is correct
28 Correct 1540 ms 44408 KB Output is correct
29 Correct 2057 ms 47480 KB Output is correct
30 Correct 3009 ms 44152 KB Output is correct
31 Correct 2450 ms 42872 KB Output is correct
32 Correct 1222 ms 40240 KB Output is correct
33 Correct 1359 ms 40320 KB Output is correct
34 Correct 800 ms 44664 KB Output is correct
35 Correct 1351 ms 43000 KB Output is correct
36 Correct 2133 ms 44956 KB Output is correct
37 Correct 2121 ms 45100 KB Output is correct
38 Correct 2061 ms 44536 KB Output is correct
39 Correct 1742 ms 43660 KB Output is correct
40 Correct 24 ms 39544 KB Output is correct

Subtask #5
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 39544 KB Output is correct
2 Correct 22 ms 39552 KB Output is correct
3 Correct 28 ms 39552 KB Output is correct
4 Correct 22 ms 39588 KB Output is correct
5 Correct 22 ms 39552 KB Output is correct
6 Correct 24 ms 39552 KB Output is correct
7 Correct 24 ms 39552 KB Output is correct
8 Correct 23 ms 39552 KB Output is correct
9 Correct 25 ms 39544 KB Output is correct
10 Correct 24 ms 39552 KB Output is correct
11 Correct 23 ms 39552 KB Output is correct
12 Correct 1303 ms 45156 KB Output is correct
13 Correct 1032 ms 45564 KB Output is correct
14 Correct 1104 ms 42160 KB Output is correct
15 Correct 1512 ms 41852 KB Output is correct
16 Correct 818 ms 41976 KB Output is correct
17 Correct 1408 ms 41920 KB Output is correct
18 Correct 1495 ms 41496 KB Output is correct
19 Correct 1817 ms 46576 KB Output is correct
20 Correct 2509 ms 42208 KB Output is correct
21 Correct 1183 ms 40232 KB Output is correct
22 Correct 2580 ms 42720 KB Output is correct
23 Correct 766 ms 43640 KB Output is correct
24 Correct 1219 ms 42488 KB Output is correct
25 Correct 2449 ms 43824 KB Output is correct
26 Correct 1893 ms 44024 KB Output is correct
27 Correct 1901 ms 43256 KB Output is correct
28 Correct 1602 ms 44408 KB Output is correct
29 Correct 2024 ms 47524 KB Output is correct
30 Correct 2944 ms 44344 KB Output is correct
31 Correct 2480 ms 43160 KB Output is correct
32 Correct 1206 ms 40184 KB Output is correct
33 Correct 1331 ms 40488 KB Output is correct
34 Correct 807 ms 44792 KB Output is correct
35 Correct 1381 ms 43000 KB Output is correct
36 Correct 2012 ms 44972 KB Output is correct
37 Correct 2125 ms 45312 KB Output is correct
38 Correct 2013 ms 44616 KB Output is correct
39 Correct 3565 ms 49828 KB Output is correct
40 Correct 4038 ms 62496 KB Output is correct
41 Correct 5172 ms 57568 KB Output is correct
42 Correct 4083 ms 54976 KB Output is correct
43 Correct 3083 ms 57312 KB Output is correct
44 Correct 709 ms 50168 KB Output is correct
45 Correct 1726 ms 53860 KB Output is correct
46 Correct 4803 ms 61348 KB Output is correct
47 Correct 4765 ms 61268 KB Output is correct
48 Correct 4683 ms 60760 KB Output is correct
49 Correct 27 ms 39552 KB Output is correct