oj.uz

Submission #281784

# Submission time Handle Problem Language Result Execution time Memory
281784 2020-08-23T13:11:33 Z Kastanda Game (IOI13_game) C++11
10 / 100
 1196 ms 22004 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 __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 6 ms 10112 KB Output is correct
2 Correct 7 ms 10112 KB Output is correct
3 Correct 7 ms 10144 KB Output is correct
4 Correct 7 ms 10112 KB Output is correct
5 Correct 7 ms 10088 KB Output is correct
6 Correct 7 ms 10112 KB Output is correct
7 Correct 7 ms 10112 KB Output is correct
8 Correct 7 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 6 ms 10112 KB Output is correct

Subtask #2
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 6 ms 10112 KB Output is correct
4 Correct 1187 ms 15736 KB Output is correct
5 Correct 956 ms 15992 KB Output is correct
6 Runtime error 45 ms 20472 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10112 KB Output is correct
2 Correct 7 ms 10112 KB Output is correct
3 Correct 7 ms 10112 KB Output is correct
4 Correct 7 ms 10112 KB Output is correct
5 Correct 7 ms 10112 KB Output is correct
6 Correct 7 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 7 ms 10112 KB Output is correct
10 Correct 7 ms 10112 KB Output is correct
11 Correct 8 ms 10112 KB Output is correct
12 Runtime error 202 ms 22004 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 10112 KB Output is correct
2 Correct 8 ms 10112 KB Output is correct
3 Correct 7 ms 10112 KB Output is correct
4 Correct 7 ms 10112 KB Output is correct
5 Correct 7 ms 10112 KB Output is correct
6 Correct 7 ms 10112 KB Output is correct
7 Correct 7 ms 10112 KB Output is correct
8 Correct 7 ms 10112 KB Output is correct
9 Correct 7 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 1196 ms 15972 KB Output is correct
13 Correct 946 ms 16120 KB Output is correct
14 Runtime error 45 ms 20472 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 10112 KB Output is correct
2 Correct 7 ms 10112 KB Output is correct
3 Correct 7 ms 10112 KB Output is correct
4 Correct 7 ms 10112 KB Output is correct
5 Correct 7 ms 10112 KB Output is correct
6 Correct 7 ms 10112 KB Output is correct
7 Correct 6 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 1193 ms 15864 KB Output is correct
13 Correct 989 ms 16120 KB Output is correct
14 Runtime error 46 ms 20472 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -