oj.uz

Submission #281776

# Submission time Handle Problem Language Result Execution time Memory
281776 2020-08-23T12:59:45 Z Kastanda Game (IOI13_game) C++11
10 / 100
 1252 ms 22904 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 = 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(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 = lower_bound(VC[id].begin(), VC[id].end(), make_pair(lq, -1)) - VC[id].begin();
                int ub = lower_bound(VC[id].begin(), VC[id].end(), make_pair(rq, -1)) - VC[id].begin() - 1;
                if (lb <= ub)
                        return GetSeg(VID[id][lb], VID[id][ub] + 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 7 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 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 6 ms 10112 KB Output is correct
9 Correct 6 ms 10112 KB Output is correct
10 Correct 8 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
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 10112 KB Output is correct
2 Correct 6 ms 10112 KB Output is correct
3 Correct 8 ms 10112 KB Output is correct
4 Correct 1240 ms 20096 KB Output is correct
5 Correct 962 ms 19984 KB Output is correct
6 Runtime error 45 ms 20856 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 8 ms 10112 KB Output is correct
2 Correct 7 ms 10112 KB Output is correct
3 Correct 8 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 8 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 10148 KB Output is correct
11 Correct 7 ms 10112 KB Output is correct
12 Runtime error 205 ms 22904 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 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 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 6 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 7 ms 10112 KB Output is correct
11 Correct 7 ms 10112 KB Output is correct
12 Correct 1252 ms 20220 KB Output is correct
13 Correct 991 ms 20020 KB Output is correct
14 Runtime error 45 ms 20852 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 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 7 ms 10112 KB Output is correct
12 Correct 1204 ms 20164 KB Output is correct
13 Correct 973 ms 20056 KB Output is correct
14 Runtime error 53 ms 20856 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -