oj.uz

Submission #281780

# Submission time Handle Problem Language Result Execution time Memory
281780 2020-08-23T13:04:00 Z Kastanda Game (IOI13_game) C++11
10 / 100
 1441 ms 201080 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 * 10, 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();
}
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 56 ms 98424 KB Output is correct
2 Correct 56 ms 98424 KB Output is correct
3 Correct 64 ms 98424 KB Output is correct
4 Correct 55 ms 98428 KB Output is correct
5 Correct 59 ms 98424 KB Output is correct
6 Correct 56 ms 98508 KB Output is correct
7 Correct 57 ms 98428 KB Output is correct
8 Correct 55 ms 98540 KB Output is correct
9 Correct 55 ms 98424 KB Output is correct
10 Correct 56 ms 98428 KB Output is correct
11 Correct 57 ms 98552 KB Output is correct
12 Correct 55 ms 98552 KB Output is correct

Subtask #2
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 55 ms 98424 KB Output is correct
2 Correct 56 ms 98424 KB Output is correct
3 Correct 56 ms 98424 KB Output is correct
4 Correct 1388 ms 104264 KB Output is correct
5 Correct 1139 ms 104600 KB Output is correct
6 Runtime error 206 ms 199648 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 56 ms 98428 KB Output is correct
2 Correct 55 ms 98424 KB Output is correct
3 Correct 62 ms 98552 KB Output is correct
4 Correct 63 ms 98428 KB Output is correct
5 Correct 58 ms 98428 KB Output is correct
6 Correct 58 ms 98424 KB Output is correct
7 Correct 57 ms 98424 KB Output is correct
8 Correct 55 ms 98508 KB Output is correct
9 Correct 62 ms 98424 KB Output is correct
10 Correct 55 ms 98424 KB Output is correct
11 Correct 56 ms 98424 KB Output is correct
12 Runtime error 373 ms 201080 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 55 ms 98556 KB Output is correct
2 Correct 57 ms 98552 KB Output is correct
3 Correct 58 ms 98552 KB Output is correct
4 Correct 55 ms 98424 KB Output is correct
5 Correct 56 ms 98424 KB Output is correct
6 Correct 56 ms 98552 KB Output is correct
7 Correct 56 ms 98520 KB Output is correct
8 Correct 57 ms 98552 KB Output is correct
9 Correct 56 ms 98424 KB Output is correct
10 Correct 55 ms 98552 KB Output is correct
11 Correct 56 ms 98552 KB Output is correct
12 Correct 1385 ms 104308 KB Output is correct
13 Correct 1144 ms 104440 KB Output is correct
14 Runtime error 206 ms 199672 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 56 ms 98424 KB Output is correct
2 Correct 56 ms 98552 KB Output is correct
3 Correct 56 ms 98552 KB Output is correct
4 Correct 55 ms 98424 KB Output is correct
5 Correct 67 ms 98424 KB Output is correct
6 Correct 57 ms 98552 KB Output is correct
7 Correct 56 ms 98424 KB Output is correct
8 Correct 55 ms 98424 KB Output is correct
9 Correct 58 ms 98552 KB Output is correct
10 Correct 63 ms 98424 KB Output is correct
11 Correct 56 ms 98424 KB Output is correct
12 Correct 1441 ms 104060 KB Output is correct
13 Correct 1155 ms 104572 KB Output is correct
14 Runtime error 204 ms 199544 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -