oj.uz

답안 #281779

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
281779 2020-08-23T13:01:22 Z Kastanda 게임 (IOI13_game) C++11
10 / 100
 1226 ms 41976 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 * 2, 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

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 19968 KB Output is correct
2 Correct 13 ms 19968 KB Output is correct
3 Correct 12 ms 19968 KB Output is correct
4 Correct 12 ms 19968 KB Output is correct
5 Correct 12 ms 19968 KB Output is correct
6 Correct 13 ms 19968 KB Output is correct
7 Correct 12 ms 19968 KB Output is correct
8 Correct 13 ms 19968 KB Output is correct
9 Correct 12 ms 19968 KB Output is correct
10 Correct 13 ms 19968 KB Output is correct
11 Correct 13 ms 19968 KB Output is correct
12 Correct 12 ms 19968 KB Output is correct

Subtask #2
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 19968 KB Output is correct
2 Correct 12 ms 20096 KB Output is correct
3 Correct 13 ms 19968 KB Output is correct
4 Correct 1226 ms 25660 KB Output is correct
5 Correct 993 ms 25956 KB Output is correct
6 Runtime error 69 ms 40440 KB Execution killed with signal 11
7 Halted 0 ms 0 KB -

Subtask #3
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 19968 KB Output is correct
2 Correct 14 ms 19968 KB Output is correct
3 Correct 13 ms 19968 KB Output is correct
4 Correct 12 ms 19968 KB Output is correct
5 Correct 13 ms 19968 KB Output is correct
6 Correct 12 ms 19968 KB Output is correct
7 Correct 14 ms 19968 KB Output is correct
8 Correct 12 ms 19968 KB Output is correct
9 Correct 14 ms 19968 KB Output is correct
10 Correct 13 ms 19968 KB Output is correct
11 Correct 12 ms 19968 KB Output is correct
12 Runtime error 222 ms 41976 KB Execution killed with signal 11
13 Halted 0 ms 0 KB -

Subtask #4
0 / 17.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 19968 KB Output is correct
2 Correct 12 ms 19968 KB Output is correct
3 Correct 13 ms 19968 KB Output is correct
4 Correct 13 ms 19968 KB Output is correct
5 Correct 12 ms 19968 KB Output is correct
6 Correct 12 ms 19968 KB Output is correct
7 Correct 12 ms 19968 KB Output is correct
8 Correct 12 ms 19968 KB Output is correct
9 Correct 13 ms 19968 KB Output is correct
10 Correct 13 ms 19968 KB Output is correct
11 Correct 12 ms 19968 KB Output is correct
12 Correct 1219 ms 25592 KB Output is correct
13 Correct 970 ms 25900 KB Output is correct
14 Runtime error 66 ms 40440 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -

Subtask #5
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 12 ms 19968 KB Output is correct
2 Correct 12 ms 19968 KB Output is correct
3 Correct 13 ms 19968 KB Output is correct
4 Correct 12 ms 19968 KB Output is correct
5 Correct 12 ms 19968 KB Output is correct
6 Correct 13 ms 19968 KB Output is correct
7 Correct 12 ms 19968 KB Output is correct
8 Correct 12 ms 19968 KB Output is correct
9 Correct 13 ms 19968 KB Output is correct
10 Correct 12 ms 19968 KB Output is correct
11 Correct 12 ms 19968 KB Output is correct
12 Correct 1222 ms 25836 KB Output is correct
13 Correct 972 ms 26104 KB Output is correct
14 Runtime error 63 ms 40440 KB Execution killed with signal 11
15 Halted 0 ms 0 KB -