제출 #351222

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
351222		idk321	Dancing Elephants (IOI11_elephants)	C++11	97 / 100	9089 ms	8764 KiB

elephants

    #include "elephants.h"
     
    #include <bits/stdc++.h>
     
    using namespace std;
    typedef long long ll;
     
     
    const int N = 150000;
    const int NS = 400;
    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 : bags[0]) cout << i<< 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();
    }

컴파일 시 표준 에러 (stderr) 메시지

elephants.cpp: In function 'void addTo(int, int, int)':
elephants.cpp:60:14: 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:14: warning: unused variable 'found' [-Wunused-variable]
   66 |         bool found = false;
      |              ^~~~~

• Subtask 1: 10 / 10
• Subtask 2: 16 / 16
• Subtask 3: 24 / 24
• Subtask 4: 47 / 47
• Subtask 5: 0 / 3