oj.uz

Submission #506091

# Submission time Handle Problem Language Result Execution time Memory
506091 2022-01-11T15:08:47 Z HappyPacMan Dancing Elephants (IOI11_elephants) C++14
100 / 100
 6430 ms 13040 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
const int sq = 391;
int qsize = 0, len;
vector<int> arr,rev,part[sq];
vector<pair<int,int> > dp[sq];
void cntdp(int sidx){
    dp[sidx].resize(part[sidx].size(),make_pair(0,0));
    for(int j=part[sidx].size();j>0;j--){
        auto it = upper_bound(part[sidx].begin(),part[sidx].end(),part[sidx][j-1]+len);
        if(it == part[sidx].end()) dp[sidx][j-1] = make_pair(1,part[sidx][j-1]+len);
        else{
            int idx = it-part[sidx].begin();
            dp[sidx][j-1] = make_pair(1+dp[sidx][idx].first,dp[sidx][idx].second);
        }
    }
}
void recalc(){
    for(int i=0;i<sq;i++){
        for(int it : part[i]) arr.emplace_back(it);
        part[i].clear();
    }
    for(int i=0;i<arr.size();i++){
        part[i/sq].push_back(arr[i]);
    }
    for(int i=0;i<sq;i++) cntdp(i);
    arr.clear();
}
int upd(int idx,int nxt){
    for(int i=0;i<sq;i++){
        if(part[i+1].empty() || nxt <= part[i].back()){
            part[i].insert(lower_bound(part[i].begin(),part[i].end(),nxt),nxt);
            cntdp(i);
            break;
        }
    }
    int curr = rev[idx];
    for(int i=0;i<sq;i++){
        if(!part[i].empty() && part[i][0] <= curr && curr <= part[i].back()){
            part[i].erase(lower_bound(part[i].begin(),part[i].end(),curr));
            cntdp(i);
            break;
        }
    }
    rev[idx] = nxt;
    int res = 0,start = -1;
    for(int i=0;i<sq;i++){
        if(upper_bound(part[i].begin(),part[i].end(),start) == part[i].end()) continue;
        int idx = upper_bound(part[i].begin(),part[i].end(),start) - part[i].begin();
        res += dp[i][idx].first;
        start = dp[i][idx].second;
    }
    return res;
}

void init(int N, int L, int X[]){
    len = L;
    for(int i=0;i<N;i++) arr.emplace_back(X[i]);
    rev.resize(N,0);
    for(int i=0;i<N;i++) rev[i] = arr[i];
    sort(arr.begin(),arr.end());
    recalc();
}

int update(int i,int y){
    if(qsize++ == sq-4){
        qsize = 0;
        recalc();
    }
    return upd(i,y);
}

Compilation message

elephants.cpp: In function 'void recalc()':
elephants.cpp:24:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   24 |     for(int i=0;i<arr.size();i++){
      |                 ~^~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 308 KB Output is correct
3 Correct 1 ms 320 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 308 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 308 KB Output is correct
6 Correct 1 ms 332 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 308 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 308 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1129 ms 2356 KB Output is correct
8 Correct 1205 ms 2728 KB Output is correct
9 Correct 868 ms 4168 KB Output is correct
10 Correct 1018 ms 3520 KB Output is correct
11 Correct 946 ms 3448 KB Output is correct
12 Correct 1314 ms 4040 KB Output is correct
13 Correct 1025 ms 3312 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 308 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 308 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1129 ms 2356 KB Output is correct
8 Correct 1205 ms 2728 KB Output is correct
9 Correct 868 ms 4168 KB Output is correct
10 Correct 1018 ms 3520 KB Output is correct
11 Correct 946 ms 3448 KB Output is correct
12 Correct 1314 ms 4040 KB Output is correct
13 Correct 1025 ms 3312 KB Output is correct
14 Correct 962 ms 3404 KB Output is correct
15 Correct 1434 ms 3556 KB Output is correct
16 Correct 2054 ms 4656 KB Output is correct
17 Correct 2128 ms 5552 KB Output is correct
18 Correct 2174 ms 5488 KB Output is correct
19 Correct 1602 ms 5068 KB Output is correct
20 Correct 2178 ms 5552 KB Output is correct
21 Correct 2302 ms 5528 KB Output is correct
22 Correct 1123 ms 4404 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 308 KB Output is correct
3 Correct 1 ms 320 KB Output is correct
4 Correct 2 ms 332 KB Output is correct
5 Correct 2 ms 308 KB Output is correct
6 Correct 1 ms 332 KB Output is correct
7 Correct 1129 ms 2356 KB Output is correct
8 Correct 1205 ms 2728 KB Output is correct
9 Correct 868 ms 4168 KB Output is correct
10 Correct 1018 ms 3520 KB Output is correct
11 Correct 946 ms 3448 KB Output is correct
12 Correct 1314 ms 4040 KB Output is correct
13 Correct 1025 ms 3312 KB Output is correct
14 Correct 962 ms 3404 KB Output is correct
15 Correct 1434 ms 3556 KB Output is correct
16 Correct 2054 ms 4656 KB Output is correct
17 Correct 2128 ms 5552 KB Output is correct
18 Correct 2174 ms 5488 KB Output is correct
19 Correct 1602 ms 5068 KB Output is correct
20 Correct 2178 ms 5552 KB Output is correct
21 Correct 2302 ms 5528 KB Output is correct
22 Correct 1123 ms 4404 KB Output is correct
23 Correct 5873 ms 12164 KB Output is correct
24 Correct 6316 ms 12192 KB Output is correct
25 Correct 3978 ms 12176 KB Output is correct
26 Correct 5459 ms 10860 KB Output is correct
27 Correct 6430 ms 10700 KB Output is correct
28 Correct 3328 ms 5184 KB Output is correct
29 Correct 3239 ms 5188 KB Output is correct
30 Correct 3301 ms 5188 KB Output is correct
31 Correct 3120 ms 5192 KB Output is correct
32 Correct 4017 ms 10288 KB Output is correct
33 Correct 3192 ms 9616 KB Output is correct
34 Correct 4307 ms 10496 KB Output is correct
35 Correct 3421 ms 13040 KB Output is correct
36 Correct 2322 ms 10260 KB Output is correct
37 Correct 5789 ms 12532 KB Output is correct
38 Correct 4326 ms 9504 KB Output is correct
39 Correct 4686 ms 10528 KB Output is correct
40 Correct 3433 ms 9524 KB Output is correct
41 Correct 6135 ms 11720 KB Output is correct
42 Correct 6188 ms 11920 KB Output is correct