Submission #136020

#	Time	Username	Problem	Language	Result	Execution time	Memory
136020		Kastanda	Game (IOI13_game)	C++11	10 / 100	3430 ms	17320 KiB

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)
    {
        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 (stderr)

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 / 10
• Subtask 2: 0 / 27
• Subtask 3: 0 / 26
• Subtask 4: 0 / 17
• Subtask 5: 0 / 20