oj.uz

답안 #351218

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
351218 2021-01-19T16:35:47 Z idk321 코끼리 (Dancing Elephants) (IOI11_elephants) C++11
97 / 100
 9000 ms 8872 KB 
#include "elephants.h"

#include <bits/stdc++.h>

using namespace std;
typedef long long ll;


const int N = 150000;
const int NS = 500;
vector<int> bags [NS];
int el[N];
int cost[NS][NS * 2 + 5];
int up[NS][NS * 2 + 5];
int n;
int l;
int used;

void bagUp(int bag)
{
    auto cbag = bags[bag];
    int j = cbag.size() - 1;
    int i = j;
    while (i >= 0)
    {
        if (cbag[i] + l >= cbag[j])
        {
            cost[bag][i] = 1;
            up[bag][i] = cbag[i] + l;
        } else
        {
            while (cbag[j - 1] - cbag[i] > l) j--;
            cost[bag][i] = cost[bag][j] + 1;
            up[bag][i] = up[bag][j];
        }

        i--;
    }
}

void rem(int node)
{
    int bag;
    for (bag = 0; bag < NS; bag++)
    {
        if (!bags[bag].empty() && el[node] <= *bags[bag].rbegin())
        {
            break;
        }
    }
    auto it = lower_bound(bags[bag].begin(), bags[bag].end(), el[node]);
    bags[bag].erase(it);
    bagUp(bag);
}

void addTo(int node, int y, int bag)
{
    auto it = bags[bag].begin();
    while(it != bags[bag].end() && *it < y) it++;
    auto cur = bags[bag].insert(it, y);
    bagUp(bag);
}

void add(int node, int y)
{
    bool found = false;
    el[node] = y;
    int bag;
    for (bag = 0; bag < NS; bag++)
    {
        if (!bags[bag].empty() && y <= *bags[bag].rbegin())
        {
            break;
        }
    }
    if (bag == NS)
    {
         bag--;
    }
    addTo(node, y, bag);
}

void make()
{
    vector<int> all;
    for (auto bag : bags) for (int i : bag) all.push_back(i);


    int c = 0;
    for (int i = 0; i < NS; i++)
    {
        bags[i].clear();
        for (int j = 0; j < NS && c < n; j++, c++)
        {
            bags[i].push_back(all[c]);
        }
    }

    for (int bag = 0; bag < NS; bag++)
    {
        bagUp(bag);
    }
}

int get()
{
    //for (int i = 0; i < NS; i++)for (int j : bags[i]) cout <<i << " "<< j<< endl;
    int last = -1;
    int res = 0;
    for (int bag = 0; bag < NS; bag++)
    {
        auto cbag = bags[bag];
        auto it = upper_bound(cbag.begin(), cbag.end(), last);
        if (it != cbag.end())
        {
            int i = it - cbag.begin();
            //cout << cbag[i] << " " << cost[bag][i] << endl;
            res += cost[bag][i];
            last = up[bag][i];
        }
    }

    return res;
}

void init(int N, int L, int X[])
{
    n = N;
    l = L;
    for (int i = 0; i < n; i++) bags[0].push_back(X[i]);
    for (int i = 0; i < n; i++) el[i] = X[i];
    make();
    used = 0;
}

int update(int ind, int y)
{
    if (used % NS == 0) make();
    rem(ind);
    add(ind, y);

    used++;
    return get();
}

Compilation message

elephants.cpp: In function 'void addTo(int, int, int)':
elephants.cpp:60:10: warning: variable 'cur' set but not used [-Wunused-but-set-variable]
   60 |     auto cur = bags[bag].insert(it, y);
      |          ^~~
elephants.cpp: In function 'void add(int, int)':
elephants.cpp:66:10: warning: unused variable 'found' [-Wunused-variable]
   66 |     bool found = false;
      |          ^~~~~

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 638 ms 1644 KB Output is correct
8 Correct 731 ms 2104 KB Output is correct
9 Correct 1118 ms 3104 KB Output is correct
10 Correct 1178 ms 3168 KB Output is correct
11 Correct 1106 ms 3220 KB Output is correct
12 Correct 1518 ms 3356 KB Output is correct
13 Correct 1229 ms 3208 KB Output is correct

Subtask #4
47.0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 638 ms 1644 KB Output is correct
8 Correct 731 ms 2104 KB Output is correct
9 Correct 1118 ms 3104 KB Output is correct
10 Correct 1178 ms 3168 KB Output is correct
11 Correct 1106 ms 3220 KB Output is correct
12 Correct 1518 ms 3356 KB Output is correct
13 Correct 1229 ms 3208 KB Output is correct
14 Correct 919 ms 2384 KB Output is correct
15 Correct 1134 ms 2456 KB Output is correct
16 Correct 2257 ms 3544 KB Output is correct
17 Correct 2731 ms 4608 KB Output is correct
18 Correct 2961 ms 4460 KB Output is correct
19 Correct 2185 ms 4704 KB Output is correct
20 Correct 2720 ms 4488 KB Output is correct
21 Correct 2741 ms 4732 KB Output is correct
22 Correct 2348 ms 4748 KB Output is correct

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Correct 1 ms 364 KB Output is correct
4 Correct 1 ms 364 KB Output is correct
5 Correct 1 ms 364 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 638 ms 1644 KB Output is correct
8 Correct 731 ms 2104 KB Output is correct
9 Correct 1118 ms 3104 KB Output is correct
10 Correct 1178 ms 3168 KB Output is correct
11 Correct 1106 ms 3220 KB Output is correct
12 Correct 1518 ms 3356 KB Output is correct
13 Correct 1229 ms 3208 KB Output is correct
14 Correct 919 ms 2384 KB Output is correct
15 Correct 1134 ms 2456 KB Output is correct
16 Correct 2257 ms 3544 KB Output is correct
17 Correct 2731 ms 4608 KB Output is correct
18 Correct 2961 ms 4460 KB Output is correct
19 Correct 2185 ms 4704 KB Output is correct
20 Correct 2720 ms 4488 KB Output is correct
21 Correct 2741 ms 4732 KB Output is correct
22 Correct 2348 ms 4748 KB Output is correct
23 Correct 8984 ms 8872 KB Output is correct
24 Execution timed out 9014 ms 8808 KB Time limit exceeded
25 Halted 0 ms 0 KB -