oj.uz

Submission #136020

# Submission time Handle Problem Language Result Execution time Memory
136020 2019-07-24T15:36:43 Z Kastanda Game (IOI13_game) C++11
10 / 100
 3430 ms 17320 KB 
// 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)
    {
        printf("%d :: %d\n", m, (int)A.size());
        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 5 ms 3192 KB Output is correct
2 Correct 5 ms 3196 KB Output is correct
3 Correct 5 ms 3320 KB Output is correct
4 Correct 4 ms 3320 KB Output is correct
5 Correct 5 ms 3320 KB Output is correct
6 Correct 4 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 3320 KB Output is correct
11 Correct 5 ms 3196 KB Output is correct
12 Correct 4 ms 3192 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3320 KB Output is correct
2 Correct 5 ms 3192 KB Output is correct
3 Correct 5 ms 3192 KB Output is correct
4 Incorrect 3224 ms 17320 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3320 KB Output is correct
2 Correct 5 ms 3320 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 3192 KB Output is correct
9 Correct 5 ms 3320 KB Output is correct
10 Correct 5 ms 3320 KB Output is correct
11 Correct 5 ms 3320 KB Output is correct
12 Incorrect 3430 ms 16796 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3320 KB Output is correct
2 Correct 5 ms 3320 KB Output is correct
3 Correct 4 ms 3192 KB Output is correct
4 Correct 6 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 5 ms 3320 KB Output is correct
9 Correct 5 ms 3192 KB Output is correct
10 Correct 5 ms 3192 KB Output is correct
11 Correct 5 ms 3192 KB Output is correct
12 Incorrect 3213 ms 17260 KB Output isn't correct
13 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 3192 KB Output is correct
2 Correct 5 ms 3192 KB Output is correct
3 Correct 5 ms 3292 KB Output is correct
4 Correct 5 ms 3192 KB Output is correct
5 Correct 5 ms 3192 KB Output is correct
6 Correct 5 ms 3192 KB Output is correct
7 Correct 5 ms 3320 KB Output is correct
8 Correct 5 ms 3320 KB Output is correct
9 Correct 4 ms 3192 KB Output is correct
10 Correct 5 ms 3196 KB Output is correct
11 Correct 5 ms 3320 KB Output is correct
12 Incorrect 3337 ms 17172 KB Output isn't correct
13 Halted 0 ms 0 KB -