oj.uz

답안 #654086

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
654086 2022-10-29T21:11:20 Z noedit 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
0 / 100
 1 ms 468 KB 
#include "elephants.h"
#include <bits/stdc++.h>

using namespace std;

const int INF = 2e9;
const int MAXN = 1e5 + 5e4;
const int B = 350;

int n, l, q = 0;

int x[MAXN + 1];

int bid[MAXN + 1];

int go[MAXN + 1];

int cnt[MAXN + 1];

vector<vector<int> > bs;



void build_block(int num)
{
    int pt = bs[num].size() - 1;
    for (int i = bs[num].size() - 1; i >= 0; i--)
    {
        if (x[bs[num][i]] + l >= x[bs[num].back()])
        {
            go[bs[num][i]] = x[bs[num][i]] + l;
            cnt[bs[num][i]] = 1;
        }
        else
        {
            while (x[bs[num][i]] + l < x[bs[num][pt]])
                pt--;
            go[bs[num][i]] = go[bs[num][pt + 1]];
            cnt[bs[num][i]] = cnt[bs[num][pt + 1]] + 1;
        }
    }
}

void build()
{
    bs.clear();
    fill(go, go + n + 1, -1);
    fill(cnt, cnt + n + 1, 1);
    bs.resize(n / B + 1);
    for (int i = 0; i < n; i++)
    {
        bs[i / B].push_back(i);
        bid[i] = i / B;
    }
    for (int i = 0; i < n / B + 1; i++)
    {
        build_block(i);
    }
}

int calc()
{
    int cur = -1;
    int ans = 0;
    for (int i = 0; i < bs.size(); i++)
    {
        auto it = upper_bound(bs[i].begin(), bs[i].end(), cur, [&](int val, int elem) {return val < x[elem];});
        if (it == bs[i].end())
        {
            continue;
        }
        ans += cnt[*it];
        cur = go[*it];
    }
    return ans;
}

void init(int N, int L, int X[])
{
    n = N;
    l = L;
    for (int i = 0; i < n; i++)
    {
        x[i] = X[i];
    }
    build();
}

int update(int i, int y)
{
    q++;
    if (q == 2 * B)
    {
        x[i] = y;
        build();
    }
    else
    {
        int pt = 0;
        for (int j = 0; j < bs[bid[i]].size(); j++)
        {
            if (bs[bid[i]][j] == i)
            {
                pt = j;
                break;
            }
        }
        bs[bid[i]].erase(bs[bid[i]].begin() + pt);
        build_block(bid[i]);
        if (y < x[i])
        {
            for (int j = 0; j <= bid[i]; j++)
            {
                if (bs[j].empty())
                    continue;
                if (x[bs[j][0]] <= y)
                {
                    pt = j;
                }
            }
        }
        else
        {
            for (int j = bid[i]; j < bs.size(); j++)
            {
                if (bs[j].empty())
                    continue;
                if (x[bs[j][0]] <= y)
                {
                    pt = j;
                }
            }
        }
        x[i] = y;
        bid[i] = pt;
        pt = bs[bid[i]].size();
        for (int j = 0; j < bs[bid[i]].size(); j++)
        {
            if (x[bs[bid[i]][j]] >= x[i])
            {
                pt = j;
                break;
            }
        }
        bs[bid[i]].insert(bs[bid[i]].begin() + pt, i);
        build_block(bid[i]);
    }
//    for (int i = 0; i < bs.size(); i++)
//    {
//        cout << i << " block: \n";
//        for (auto& j : bs[i])
//            cout << j << " " << x[j] << endl;
//    }
    return calc();
}

Compilation message

elephants.cpp: In function 'int calc()':
elephants.cpp:65:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |     for (int i = 0; i < bs.size(); i++)
      |                     ~~^~~~~~~~~~~
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:100:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  100 |         for (int j = 0; j < bs[bid[i]].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~~~~
elephants.cpp:124:36: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  124 |             for (int j = bid[i]; j < bs.size(); j++)
      |                                  ~~^~~~~~~~~~~
elephants.cpp:137:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  137 |         for (int j = 0; j < bs[bid[i]].size(); j++)
      |                         ~~^~~~~~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 468 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -