oj.uz

Submission #565660

# Submission time Handle Problem Language Result Execution time Memory
565660 2022-05-21T08:36:55 Z qwerasdfzxcl Dancing Elephants (IOI11_elephants) C++14
26 / 100
 18 ms 2512 KB 
#include "elephants.h"
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;
const int INF = 1e9+100, B = 400;
int l;
struct Bucket{
    vector<pair<int, int>> X;
    vector<int> dp, dp2;
    Bucket(){}

    void push(int x, int ii, bool _ins = 0){
        if (!_ins) {X.emplace_back(x, ii); return;}

        for (int i=0;i<(int)X.size();i++) if (x <= X[i].first){
            X.insert(X.begin()+i, make_pair(x, ii));
            return;
        }
        X.insert(X.end(), make_pair(x, ii));
    }
    void _delete(int x, int i){
        for (auto iter = X.begin();iter!=X.end();iter++){
            if (iter->first==x && iter->second==i){
                X.erase(iter);
                return;
            }
        }
        //for (auto &p:X) printf("[%d %d] ", p.first, p.second);
        //printf("\n%d %d\n", x, i);
        assert(0);
    }
    void build(){
        dp.clear();
        dp2.clear();
        dp.resize(X.size(), -1);
        dp2.resize(X.size(), 1);

        int pt = (int)X.size()-1;
        for (int i=(int)X.size()-1;i>=0;i--){
            while(pt>i && X[i].first + l < X[pt].first) pt--;
            if (pt+1==(int)X.size()) {dp[i] = X[i].first; continue;}

            dp[i] = dp[pt+1];
            dp2[i] = dp2[pt+1] + 1;
        }
    }

    pair<int, int> get_nxt(int prv){
        auto iter = lower_bound(X.begin(), X.end(), make_pair(prv+l+1, -1));
        if (iter==X.end()) return {0, prv};
        int i = iter - X.begin();
        return {dp2[i], dp[i]};
    }
}buc[404];

const int BQ = 400;
int n, a[150150], bidx[150150], q, cntq = 0, cntb;
set<pair<int, int>> st;

void rebuild(){
    auto iter = st.begin();
    for (int i=0;true;i++){
        //printf(" YYES\n");
        buc[i].X.clear();

        for (int j=0;j<B;j++){
            if (iter==st.end()) break;
            buc[i].push(iter->first, iter->second);
            bidx[iter->second] = i;
            ++iter;
        }

        buc[i].build();
        cntb = i+1;
        if (iter==st.end()) break;
    }
}

void init(int N, int L, int X[])
{
    n = N, l = L;
    for (int i=0;i<N;i++){
        a[i+1] = X[i];
        st.emplace(a[i+1], i+1);
    }

    //printf("YES\n");
    rebuild();
}

int update(int I, int y)
{
    //printf("YES\n");
    if (n==1) return 1;

    I++;
    if (cntq==BQ){
        cntq = 0; rebuild();
    }
    cntq++;

    ///delete
    buc[bidx[I]]._delete(a[I], I);
    st.erase(st.find(make_pair(a[I], I)));
    buc[bidx[I]].build();

    ///push
    a[I] = y;
    auto iter = st.insert(make_pair(a[I], I)).first;
    if (iter==st.end()) bidx[I] = bidx[prev(iter)->second];
    else bidx[I] = bidx[next(iter)->second];
    buc[bidx[I]].push(a[I], I, 1);
    buc[bidx[I]].build();

    ///calculate
    int s = -INF, ans = 0;
    for (int i=0;i<cntb;i++){
        auto [cnt, nxt] = buc[i].get_nxt(s);
        ans += cnt;
        s = nxt;
    }

    //printf(" %d\n", ans);
    //for (auto &p:buc[0].X) printf("[%d %d] ", p.first, p.second);
    //printf("\n");
    return ans;
}

Compilation message

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:119:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  119 |         auto [cnt, nxt] = buc[i].get_nxt(s);
      |              ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 396 KB Output is correct
3 Correct 1 ms 344 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 396 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 396 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Incorrect 18 ms 2512 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 396 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Incorrect 18 ms 2512 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 396 KB Output is correct
3 Correct 1 ms 344 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Incorrect 18 ms 2512 KB Output isn't correct
8 Halted 0 ms 0 KB -