Submission #136024

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
136024	2019-07-24T15:44:05 Z	Kastanda	Game (IOI13_game)	C++11	100 / 100	4875 ms	28800 KB

game

// ItnoE
#include<bits/stdc++.h>
#include "game.h"
using namespace std;
typedef long long ll;
const int N = 22005, SQ = 800;
int n, X[N], Y[N], P[N], rev[N];
ll Z[N];
vector < int > UX, UY, V[N];
map < pair < int , int > , int > MP;
struct Tree
{
    int m;
    vector < ll > G;
    vector < int > A;
    inline void Build()
    {
        m = (int)A.size();
        G.resize(m + m);
        for (int i = 0; i < m; i ++)
            G[i + m] = Z[A[i]];
        for (int i = m - 1; i; i --)
            G[i] = __gcd(G[i << 1], G[i << 1 ^ 1]);
    }
    inline void Set(int i)
    {
        G[i + m] = Z[A[i]];
        for (i += m; i > 1; i >>= 1)
            G[i >> 1] = __gcd(G[i], G[i ^ 1]);
    }
    inline ll Get(int l, int r)
    {
        ll g = 0;
        for (l += m, r += m; l < r; l >>= 1, r >>= 1)
        {
            if (l & 1) g = __gcd(g, G[l ++]);
            if (r & 1) g = __gcd(g, G[-- r]);
        }
        return (g);
    }
};
Tree S[N * 2];
inline bool CMPY(int i, int j)
{
    return (Y[i] < Y[j]);
}
inline void Build()
{
    int m = (int)UX.size();
    for (int i = m; i < m + m; i ++)
        S[i].A = vector < int > {rev[i - m]}, S[i].Build();
    for (int i = m - 1; i; i --)
    {
        int lc = i << 1, rc = lc ^ 1;
        S[i].A.clear();
        merge(S[lc].A.begin(), S[lc].A.end(), S[rc].A.begin(), S[rc].A.end(), back_inserter(S[i].A), CMPY);
        S[i].Build();
    }
    for (int i = 0; i < n; i ++)
        V[i].clear();
    for (int i = m + m - 1; i; i --)
        for (int j = 0; j < S[i].m; j ++)
            V[S[i].A[j]].push_back(j);
}
inline void Set(int i)
{
    int id = rev[i], ptr = 0;
    for (i += (int)UX.size(); i; i >>= 1)
        S[i].Set(V[id][ptr]), ptr ++;
}
inline ll Get(int l, int r, int le, int ri)
{
    ll g = 0;
    for (l += (int)UX.size(), r += (int)UX.size(); l < r; l >>= 1, r >>= 1)
    {
        if (l & 1)
        {
            int lb = lower_bound(S[l].A.begin(), S[l].A.end(), le, CMPY) - S[l].A.begin();
            int ub = lower_bound(S[l].A.begin(), S[l].A.end(), ri, CMPY) - S[l].A.begin();
            g = __gcd(g, S[l].Get(lb, ub));
            l ++;
        }
        if (r & 1)
        {
            r --;
            int lb = lower_bound(S[r].A.begin(), S[r].A.end(), le, CMPY) - S[r].A.begin();
            int ub = lower_bound(S[r].A.begin(), S[r].A.end(), ri, CMPY) - S[r].A.begin();
            g = __gcd(g, S[r].Get(lb, ub));
        }
    }
    return (g);
}
inline void Init()
{
    UX.clear();
    UY.clear();
    for (int i = 0; i < n; i ++)
        UX.push_back(X[i]),
        UY.push_back(Y[i]);
    sort(UX.begin(), UX.end());
    sort(UY.begin(), UY.end());
    memset(rev, -1, sizeof(rev));
    for (int i = 0; i < n; i ++)
    {
        int lb = lower_bound(UX.begin(), UX.end(), X[i]) - UX.begin();
        while (~ rev[lb]) lb ++;
        rev[lb] = i;
        P[i] = lb;
    }
    Build();
}
void init(int _, int __)
{

}
void update(int a, int b, ll c)
{
    if (MP.count({a, b}))
    {
        int i = MP[{a, b}];
        Z[i] = c;
        if (i < n / SQ * SQ)
            Set(P[i]);
        return ;
    }
    MP[{a, b}] = n;
    X[n] = a; Y[n] = b; Z[n] = c; n ++;
    if (n % SQ == 0)
        Init();
}
ll calculate(int a, int b, int c, int d)
{
    if (a > c) swap(a, c);
    if (b > d) swap(b, d);
    c ++; d ++;

    int aa = lower_bound(UX.begin(), UX.end(), a) - UX.begin();
    int cc = lower_bound(UX.begin(), UX.end(), c) - UX.begin();
    Y[n + 1] = b; Y[n + 2] = d;
    ll g = Get(aa, cc, n + 1, n + 2);
    for (int i = n / SQ * SQ; i < n; i ++)
        if (a <= X[i] && X[i] < c && b <= Y[i] && Y[i] < d)
            g = __gcd(g, Z[i]);
    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]
  int res;
      ^~~

Subtask #1

10.0 / 10.0

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

Subtask #2

27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	3192 KB	Output is correct
2	Correct	4 ms	3192 KB	Output is correct
3	Correct	4 ms	3192 KB	Output is correct
4	Correct	3229 ms	13004 KB	Output is correct
5	Correct	2450 ms	17008 KB	Output is correct
6	Correct	2267 ms	14440 KB	Output is correct
7	Correct	2548 ms	14244 KB	Output is correct
8	Correct	1399 ms	11496 KB	Output is correct
9	Correct	2397 ms	14252 KB	Output is correct
10	Correct	2341 ms	13888 KB	Output is correct
11	Correct	5 ms	3192 KB	Output is correct

Subtask #3

26.0 / 26.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	3192 KB	Output is correct
2	Correct	4 ms	3192 KB	Output is correct
3	Correct	6 ms	3240 KB	Output is correct
4	Correct	4 ms	3192 KB	Output is correct
5	Correct	4 ms	3192 KB	Output is correct
6	Correct	4 ms	3252 KB	Output is correct
7	Correct	4 ms	3192 KB	Output is correct
8	Correct	4 ms	3368 KB	Output is correct
9	Correct	4 ms	3192 KB	Output is correct
10	Correct	4 ms	3192 KB	Output is correct
11	Correct	4 ms	3196 KB	Output is correct
12	Correct	3420 ms	12684 KB	Output is correct
13	Correct	3909 ms	11496 KB	Output is correct
14	Correct	1333 ms	8496 KB	Output is correct
15	Correct	3632 ms	12612 KB	Output is correct
16	Correct	3437 ms	13748 KB	Output is correct
17	Correct	1627 ms	11940 KB	Output is correct
18	Correct	2449 ms	15044 KB	Output is correct
19	Correct	2302 ms	15140 KB	Output is correct
20	Correct	2196 ms	14612 KB	Output is correct
21	Correct	5 ms	3192 KB	Output is correct

Subtask #4

17.0 / 17.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	6 ms	3320 KB	Output is correct
2	Correct	5 ms	3192 KB	Output is correct
3	Correct	5 ms	3320 KB	Output is correct
4	Correct	5 ms	3320 KB	Output is correct
5	Correct	5 ms	3320 KB	Output is correct
6	Correct	5 ms	3320 KB	Output is correct
7	Correct	5 ms	3320 KB	Output is correct
8	Correct	5 ms	3320 KB	Output is correct
9	Correct	5 ms	3192 KB	Output is correct
10	Correct	5 ms	3292 KB	Output is correct
11	Correct	5 ms	3192 KB	Output is correct
12	Correct	3196 ms	12824 KB	Output is correct
13	Correct	2427 ms	17064 KB	Output is correct
14	Correct	2168 ms	14480 KB	Output is correct
15	Correct	2496 ms	14148 KB	Output is correct
16	Correct	1343 ms	11488 KB	Output is correct
17	Correct	2310 ms	14176 KB	Output is correct
18	Correct	2322 ms	14080 KB	Output is correct
19	Correct	3440 ms	16844 KB	Output is correct
20	Correct	3800 ms	11572 KB	Output is correct
21	Correct	1326 ms	8596 KB	Output is correct
22	Correct	3586 ms	12568 KB	Output is correct
23	Correct	3440 ms	13796 KB	Output is correct
24	Correct	1630 ms	11800 KB	Output is correct
25	Correct	2471 ms	15052 KB	Output is correct
26	Correct	2251 ms	15280 KB	Output is correct
27	Correct	2209 ms	14696 KB	Output is correct
28	Correct	1090 ms	19792 KB	Output is correct
29	Correct	3468 ms	22320 KB	Output is correct
30	Correct	3314 ms	16292 KB	Output is correct
31	Correct	2954 ms	15052 KB	Output is correct
32	Correct	1365 ms	13148 KB	Output is correct
33	Correct	2405 ms	13012 KB	Output is correct
34	Correct	3466 ms	16248 KB	Output is correct
35	Correct	1708 ms	17180 KB	Output is correct
36	Correct	2552 ms	20384 KB	Output is correct
37	Correct	2379 ms	20560 KB	Output is correct
38	Correct	2286 ms	19860 KB	Output is correct
39	Correct	1947 ms	18856 KB	Output is correct
40	Correct	4 ms	3320 KB	Output is correct

Subtask #5

20.0 / 20.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	5 ms	3320 KB	Output is correct
2	Correct	5 ms	3324 KB	Output is correct
3	Correct	4 ms	3192 KB	Output is correct
4	Correct	4 ms	3320 KB	Output is correct
5	Correct	4 ms	3192 KB	Output is correct
6	Correct	5 ms	3320 KB	Output is correct
7	Correct	5 ms	3192 KB	Output is correct
8	Correct	4 ms	3320 KB	Output is correct
9	Correct	6 ms	3320 KB	Output is correct
10	Correct	6 ms	3320 KB	Output is correct
11	Correct	5 ms	3328 KB	Output is correct
12	Correct	3201 ms	13168 KB	Output is correct
13	Correct	2418 ms	17148 KB	Output is correct
14	Correct	2155 ms	14272 KB	Output is correct
15	Correct	2464 ms	14200 KB	Output is correct
16	Correct	1337 ms	11396 KB	Output is correct
17	Correct	2360 ms	14280 KB	Output is correct
18	Correct	2325 ms	13912 KB	Output is correct
19	Correct	3407 ms	16912 KB	Output is correct
20	Correct	3782 ms	11516 KB	Output is correct
21	Correct	1328 ms	8540 KB	Output is correct
22	Correct	3604 ms	12792 KB	Output is correct
23	Correct	3465 ms	13548 KB	Output is correct
24	Correct	1609 ms	11972 KB	Output is correct
25	Correct	2446 ms	15124 KB	Output is correct
26	Correct	2192 ms	15116 KB	Output is correct
27	Correct	2219 ms	14772 KB	Output is correct
28	Correct	1060 ms	19808 KB	Output is correct
29	Correct	3450 ms	22592 KB	Output is correct
30	Correct	3315 ms	16324 KB	Output is correct
31	Correct	2972 ms	15116 KB	Output is correct
32	Correct	1369 ms	13088 KB	Output is correct
33	Correct	2400 ms	13184 KB	Output is correct
34	Correct	3464 ms	16268 KB	Output is correct
35	Correct	1682 ms	17200 KB	Output is correct
36	Correct	2564 ms	20236 KB	Output is correct
37	Correct	2217 ms	20604 KB	Output is correct
38	Correct	2280 ms	20008 KB	Output is correct
39	Correct	1526 ms	26768 KB	Output is correct
40	Correct	4253 ms	28800 KB	Output is correct
41	Correct	3928 ms	23508 KB	Output is correct
42	Correct	3688 ms	20320 KB	Output is correct
43	Correct	4875 ms	23572 KB	Output is correct
44	Correct	909 ms	13836 KB	Output is correct
45	Correct	1979 ms	19004 KB	Output is correct
46	Correct	3483 ms	27560 KB	Output is correct
47	Correct	3461 ms	27588 KB	Output is correct
48	Correct	4241 ms	27276 KB	Output is correct
49	Correct	5 ms	3320 KB	Output is correct