oj.uz

Submission #565665

# Submission time Handle Problem Language Result Execution time Memory
565665 2022-05-21T08:46:42 Z qwerasdfzxcl Dancing Elephants (IOI11_elephants) C++14
100 / 100
 4864 ms 20508 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 (next(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 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 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
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 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 Correct 428 ms 2252 KB Output is correct
8 Correct 429 ms 3616 KB Output is correct
9 Correct 413 ms 6380 KB Output is correct
10 Correct 407 ms 6176 KB Output is correct
11 Correct 397 ms 6220 KB Output is correct
12 Correct 735 ms 6444 KB Output is correct
13 Correct 429 ms 5968 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 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 Correct 428 ms 2252 KB Output is correct
8 Correct 429 ms 3616 KB Output is correct
9 Correct 413 ms 6380 KB Output is correct
10 Correct 407 ms 6176 KB Output is correct
11 Correct 397 ms 6220 KB Output is correct
12 Correct 735 ms 6444 KB Output is correct
13 Correct 429 ms 5968 KB Output is correct
14 Correct 422 ms 4232 KB Output is correct
15 Correct 587 ms 4404 KB Output is correct
16 Correct 1129 ms 6968 KB Output is correct
17 Correct 1128 ms 8836 KB Output is correct
18 Correct 1200 ms 8908 KB Output is correct
19 Correct 562 ms 8796 KB Output is correct
20 Correct 1085 ms 8896 KB Output is correct
21 Correct 1117 ms 8856 KB Output is correct
22 Correct 631 ms 8224 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 1 ms 340 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 Correct 428 ms 2252 KB Output is correct
8 Correct 429 ms 3616 KB Output is correct
9 Correct 413 ms 6380 KB Output is correct
10 Correct 407 ms 6176 KB Output is correct
11 Correct 397 ms 6220 KB Output is correct
12 Correct 735 ms 6444 KB Output is correct
13 Correct 429 ms 5968 KB Output is correct
14 Correct 422 ms 4232 KB Output is correct
15 Correct 587 ms 4404 KB Output is correct
16 Correct 1129 ms 6968 KB Output is correct
17 Correct 1128 ms 8836 KB Output is correct
18 Correct 1200 ms 8908 KB Output is correct
19 Correct 562 ms 8796 KB Output is correct
20 Correct 1085 ms 8896 KB Output is correct
21 Correct 1117 ms 8856 KB Output is correct
22 Correct 631 ms 8224 KB Output is correct
23 Correct 3383 ms 18784 KB Output is correct
24 Correct 3286 ms 18844 KB Output is correct
25 Correct 2426 ms 18784 KB Output is correct
26 Correct 2882 ms 18864 KB Output is correct
27 Correct 2977 ms 18656 KB Output is correct
28 Correct 1179 ms 5440 KB Output is correct
29 Correct 1128 ms 5464 KB Output is correct
30 Correct 1165 ms 5448 KB Output is correct
31 Correct 1128 ms 5532 KB Output is correct
32 Correct 2450 ms 18232 KB Output is correct
33 Correct 2176 ms 17556 KB Output is correct
34 Correct 2396 ms 18440 KB Output is correct
35 Correct 2098 ms 18728 KB Output is correct
36 Correct 2093 ms 18200 KB Output is correct
37 Correct 4467 ms 20508 KB Output is correct
38 Correct 2534 ms 17444 KB Output is correct
39 Correct 2284 ms 18484 KB Output is correct
40 Correct 2552 ms 17588 KB Output is correct
41 Correct 4864 ms 18624 KB Output is correct
42 Correct 4843 ms 18828 KB Output is correct