oj.uz

Submission #281793

# Submission time Handle Problem Language Result Execution time Memory
281793 2020-08-23T13:25:54 Z Kastanda Game (IOI13_game) C++14
80 / 100
 3305 ms 50604 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, 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 0LL;
        }
        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;
      |      ^~~
game.cpp: In function 'll Get(int, int, int, int, int, int, int)':
game.cpp:114:17: warning: this 'if' clause does not guard... [-Wmisleading-indentation]
  114 |                 if (lb < ub)
      |                 ^~
game.cpp:116:13: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'if'
  116 |             return 0LL;
      |             ^~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10112 KB Output is correct
2 Correct 6 ms 10112 KB Output is correct
3 Correct 7 ms 10112 KB Output is correct
4 Correct 6 ms 10112 KB Output is correct
5 Correct 6 ms 10240 KB Output is correct
6 Correct 6 ms 10112 KB Output is correct
7 Correct 6 ms 10112 KB Output is correct
8 Correct 7 ms 10112 KB Output is correct
9 Correct 6 ms 10112 KB Output is correct
10 Correct 7 ms 10112 KB Output is correct
11 Correct 6 ms 10112 KB Output is correct
12 Correct 6 ms 10112 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10112 KB Output is correct
2 Correct 6 ms 10112 KB Output is correct
3 Correct 7 ms 10112 KB Output is correct
4 Correct 1210 ms 15720 KB Output is correct
5 Correct 977 ms 16120 KB Output is correct
6 Correct 1041 ms 17072 KB Output is correct
7 Correct 1445 ms 17012 KB Output is correct
8 Correct 771 ms 16724 KB Output is correct
9 Correct 1322 ms 17440 KB Output is correct
10 Correct 1392 ms 16852 KB Output is correct
11 Correct 6 ms 10112 KB Output is correct

Subtask #3
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10112 KB Output is correct
2 Correct 6 ms 10112 KB Output is correct
3 Correct 7 ms 10112 KB Output is correct
4 Correct 6 ms 10112 KB Output is correct
5 Correct 6 ms 10112 KB Output is correct
6 Correct 6 ms 10112 KB Output is correct
7 Correct 7 ms 10112 KB Output is correct
8 Correct 6 ms 10112 KB Output is correct
9 Correct 6 ms 10112 KB Output is correct
10 Correct 6 ms 10112 KB Output is correct
11 Correct 6 ms 10112 KB Output is correct
12 Correct 1719 ms 16948 KB Output is correct
13 Correct 2486 ms 16848 KB Output is correct
14 Correct 1173 ms 15352 KB Output is correct
15 Correct 2533 ms 17912 KB Output is correct
16 Correct 715 ms 18296 KB Output is correct
17 Correct 1189 ms 18040 KB Output is correct
18 Correct 2415 ms 19764 KB Output is correct
19 Correct 1866 ms 19740 KB Output is correct
20 Correct 1886 ms 19404 KB Output is correct
21 Correct 6 ms 10112 KB Output is correct

Subtask #4
17.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10112 KB Output is correct
2 Correct 6 ms 10112 KB Output is correct
3 Correct 6 ms 10112 KB Output is correct
4 Correct 6 ms 10112 KB Output is correct
5 Correct 6 ms 10112 KB Output is correct
6 Correct 6 ms 10112 KB Output is correct
7 Correct 6 ms 10112 KB Output is correct
8 Correct 7 ms 10112 KB Output is correct
9 Correct 6 ms 10112 KB Output is correct
10 Correct 6 ms 10112 KB Output is correct
11 Correct 6 ms 10112 KB Output is correct
12 Correct 1197 ms 15756 KB Output is correct
13 Correct 959 ms 16084 KB Output is correct
14 Correct 1028 ms 16804 KB Output is correct
15 Correct 1476 ms 17260 KB Output is correct
16 Correct 782 ms 16984 KB Output is correct
17 Correct 1327 ms 17144 KB Output is correct
18 Correct 1357 ms 17000 KB Output is correct
19 Correct 1743 ms 21152 KB Output is correct
20 Correct 2403 ms 17032 KB Output is correct
21 Correct 1168 ms 15648 KB Output is correct
22 Correct 2454 ms 17744 KB Output is correct
23 Correct 713 ms 18296 KB Output is correct
24 Correct 1194 ms 18100 KB Output is correct
25 Correct 2373 ms 19832 KB Output is correct
26 Correct 1893 ms 19868 KB Output is correct
27 Correct 1762 ms 19396 KB Output is correct
28 Correct 1422 ms 25592 KB Output is correct
29 Correct 1932 ms 28156 KB Output is correct
30 Correct 2873 ms 21796 KB Output is correct
31 Correct 2458 ms 20588 KB Output is correct
32 Correct 1199 ms 19960 KB Output is correct
33 Correct 1328 ms 20152 KB Output is correct
34 Correct 784 ms 22008 KB Output is correct
35 Correct 1387 ms 23420 KB Output is correct
36 Correct 2019 ms 26240 KB Output is correct
37 Correct 2045 ms 26392 KB Output is correct
38 Correct 1968 ms 25664 KB Output is correct
39 Correct 1664 ms 24568 KB Output is correct
40 Correct 6 ms 10112 KB Output is correct

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10144 KB Output is correct
2 Correct 6 ms 10112 KB Output is correct
3 Correct 6 ms 10112 KB Output is correct
4 Correct 6 ms 10112 KB Output is correct
5 Correct 7 ms 10112 KB Output is correct
6 Correct 6 ms 10112 KB Output is correct
7 Correct 7 ms 10112 KB Output is correct
8 Correct 6 ms 10112 KB Output is correct
9 Correct 7 ms 10112 KB Output is correct
10 Correct 7 ms 10112 KB Output is correct
11 Correct 7 ms 10112 KB Output is correct
12 Correct 1201 ms 16120 KB Output is correct
13 Correct 940 ms 16124 KB Output is correct
14 Correct 1042 ms 17272 KB Output is correct
15 Correct 1442 ms 17016 KB Output is correct
16 Correct 767 ms 16776 KB Output is correct
17 Correct 1330 ms 17104 KB Output is correct
18 Correct 1420 ms 16704 KB Output is correct
19 Correct 1788 ms 21112 KB Output is correct
20 Correct 2431 ms 16892 KB Output is correct
21 Correct 1157 ms 15480 KB Output is correct
22 Correct 2483 ms 17616 KB Output is correct
23 Correct 733 ms 18340 KB Output is correct
24 Correct 1206 ms 17880 KB Output is correct
25 Correct 2378 ms 20004 KB Output is correct
26 Correct 1831 ms 19720 KB Output is correct
27 Correct 1759 ms 19192 KB Output is correct
28 Correct 1470 ms 25572 KB Output is correct
29 Correct 1966 ms 28256 KB Output is correct
30 Correct 2842 ms 21880 KB Output is correct
31 Correct 2438 ms 20480 KB Output is correct
32 Correct 1235 ms 19960 KB Output is correct
33 Correct 1360 ms 20044 KB Output is correct
34 Correct 807 ms 22008 KB Output is correct
35 Correct 1331 ms 23248 KB Output is correct
36 Correct 1905 ms 26140 KB Output is correct
37 Correct 2048 ms 26236 KB Output is correct
38 Correct 1994 ms 25708 KB Output is correct
39 Runtime error 3305 ms 50604 KB Execution killed with signal 11
40 Halted 0 ms 0 KB -