oj.uz

Submission #465412

# Submission time Handle Problem Language Result Execution time Memory
465412 2021-08-16T00:43:51 Z JovanB Dancing Elephants (IOI11_elephants) C++17
100 / 100
 4155 ms 17992 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;

int n, k;

const int N = 150000;
const int K = 400;

int dp[N+5], dokle[N+5], pos[N+5];
vector <pair <int, int>> vec[N+5];

void Calc(int tr){
    if(vec[tr].empty()) return;
    int j = vec[tr].size() - 1;
    for(int i=vec[tr].size()-1; i>=0; i--){
        while(vec[tr][i].first + k - 1 < vec[tr][j].first) j--;
        if(j == vec[tr].size() - 1){
            dp[vec[tr][i].second] = 1;
            dokle[vec[tr][i].second] = vec[tr][i].first + k - 1;
        }
        else{
            dp[vec[tr][i].second] = dp[vec[tr][j+1].second] + 1;
            dokle[vec[tr][i].second] = dokle[vec[tr][j+1].second];
        }
    }
}

void Build(const vector <pair <int, int>> &v){
    for(int i=1; i<=n; i++) vec[i].clear();
    int tr = 1;
    for(auto c : v){
        if(vec[tr].size() > K){
            Calc(tr);
            tr++;
        }
        vec[tr].push_back(c);
    }
    Calc(tr);
}

void Rebuild(){
    vector <pair <int, int>> v;
    for(int i=1; i<=n/K+2; i++) for(auto c : vec[i]) v.push_back(c);
    Build(v);
}

int query(){
    int tr = -1, res = 0;
    for(int i=1; i<=n/K+2; i++){
        auto x = upper_bound(vec[i].begin(), vec[i].end(), make_pair(tr, n+5));
        if(x == vec[i].end()) continue;
        res += dp[x->second];
        tr = dokle[x->second];
    }
    return res;
}

void init(int _n, int L, int X[]){
    n = _n, k = L + 1;
    vector <pair <int, int>> x;
    for(int i=0; i<n; i++){
        pos[i] = X[i];
        x.push_back({X[i], i});
    }
    Build(x);
}

void brisi(int ind, int tr){
    for(int i=0; i<vec[tr].size(); i++){
        if(vec[tr][i] == make_pair(pos[ind], ind)){
            vec[tr].erase(vec[tr].begin() + i);
            return;
        }
    }
}

void dodaj(int ind, int tr){
    for(int i=0; i<vec[tr].size(); i++){
        if(vec[tr][i] > make_pair(pos[ind], ind)){
            vec[tr].insert(vec[tr].begin() + i, {pos[ind], ind});
            return;
        }
    }
    vec[tr].push_back({pos[ind], ind});
    return;
}

int update(int ind, int y){
    int gde = 1;
    for(int i=1; i<=2+n/K; i++){
        if(vec[i].empty()) continue;
        gde = i;
        if(make_pair(pos[ind], ind) <= vec[i].back()) break;
    }
    brisi(ind, gde);
    Calc(gde);
    pos[ind] = y;
    gde = 1;
    for(int i=1; i<=2+n/K; i++){
        if(vec[i].empty()) continue;
        gde = i;
        if(make_pair(pos[ind], ind) <= vec[i].back()) break;
    }
    dodaj(ind, gde);
    Calc(gde);
    if(vec[gde].size() > 2*K) Rebuild();
    return query();
}

Compilation message

elephants.cpp: In function 'void Calc(int)':
elephants.cpp:18:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   18 |         if(j == vec[tr].size() - 1){
      |            ~~^~~~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'void brisi(int, int)':
elephants.cpp:70:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   70 |     for(int i=0; i<vec[tr].size(); i++){
      |                  ~^~~~~~~~~~~~~~~
elephants.cpp: In function 'void dodaj(int, int)':
elephants.cpp:79:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |     for(int i=0; i<vec[tr].size(); i++){
      |                  ~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3788 KB Output is correct
2 Correct 2 ms 3744 KB Output is correct
3 Correct 3 ms 3788 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3788 KB Output is correct
2 Correct 2 ms 3744 KB Output is correct
3 Correct 3 ms 3788 KB Output is correct
4 Correct 2 ms 3788 KB Output is correct
5 Correct 3 ms 3788 KB Output is correct
6 Correct 3 ms 3788 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3788 KB Output is correct
2 Correct 2 ms 3744 KB Output is correct
3 Correct 3 ms 3788 KB Output is correct
4 Correct 2 ms 3788 KB Output is correct
5 Correct 3 ms 3788 KB Output is correct
6 Correct 3 ms 3788 KB Output is correct
7 Correct 412 ms 5084 KB Output is correct
8 Correct 459 ms 5552 KB Output is correct
9 Correct 473 ms 6084 KB Output is correct
10 Correct 563 ms 6644 KB Output is correct
11 Correct 617 ms 6876 KB Output is correct
12 Correct 696 ms 6788 KB Output is correct
13 Correct 580 ms 6588 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3788 KB Output is correct
2 Correct 2 ms 3744 KB Output is correct
3 Correct 3 ms 3788 KB Output is correct
4 Correct 2 ms 3788 KB Output is correct
5 Correct 3 ms 3788 KB Output is correct
6 Correct 3 ms 3788 KB Output is correct
7 Correct 412 ms 5084 KB Output is correct
8 Correct 459 ms 5552 KB Output is correct
9 Correct 473 ms 6084 KB Output is correct
10 Correct 563 ms 6644 KB Output is correct
11 Correct 617 ms 6876 KB Output is correct
12 Correct 696 ms 6788 KB Output is correct
13 Correct 580 ms 6588 KB Output is correct
14 Correct 606 ms 5628 KB Output is correct
15 Correct 605 ms 5436 KB Output is correct
16 Correct 1008 ms 6332 KB Output is correct
17 Correct 1084 ms 10196 KB Output is correct
18 Correct 1181 ms 10260 KB Output is correct
19 Correct 1004 ms 10308 KB Output is correct
20 Correct 1077 ms 10176 KB Output is correct
21 Correct 1107 ms 10300 KB Output is correct
22 Correct 926 ms 9968 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 3788 KB Output is correct
2 Correct 2 ms 3744 KB Output is correct
3 Correct 3 ms 3788 KB Output is correct
4 Correct 2 ms 3788 KB Output is correct
5 Correct 3 ms 3788 KB Output is correct
6 Correct 3 ms 3788 KB Output is correct
7 Correct 412 ms 5084 KB Output is correct
8 Correct 459 ms 5552 KB Output is correct
9 Correct 473 ms 6084 KB Output is correct
10 Correct 563 ms 6644 KB Output is correct
11 Correct 617 ms 6876 KB Output is correct
12 Correct 696 ms 6788 KB Output is correct
13 Correct 580 ms 6588 KB Output is correct
14 Correct 606 ms 5628 KB Output is correct
15 Correct 605 ms 5436 KB Output is correct
16 Correct 1008 ms 6332 KB Output is correct
17 Correct 1084 ms 10196 KB Output is correct
18 Correct 1181 ms 10260 KB Output is correct
19 Correct 1004 ms 10308 KB Output is correct
20 Correct 1077 ms 10176 KB Output is correct
21 Correct 1107 ms 10300 KB Output is correct
22 Correct 926 ms 9968 KB Output is correct
23 Correct 2514 ms 15668 KB Output is correct
24 Correct 2722 ms 15540 KB Output is correct
25 Correct 2324 ms 15544 KB Output is correct
26 Correct 3074 ms 17992 KB Output is correct
27 Correct 4155 ms 17888 KB Output is correct
28 Correct 1651 ms 8904 KB Output is correct
29 Correct 1624 ms 8900 KB Output is correct
30 Correct 1643 ms 8896 KB Output is correct
31 Correct 1640 ms 8912 KB Output is correct
32 Correct 3282 ms 17280 KB Output is correct
33 Correct 2665 ms 16672 KB Output is correct
34 Correct 2743 ms 17556 KB Output is correct
35 Correct 2701 ms 17768 KB Output is correct
36 Correct 2175 ms 15028 KB Output is correct
37 Correct 2857 ms 17584 KB Output is correct
38 Correct 2891 ms 16544 KB Output is correct
39 Correct 3701 ms 17608 KB Output is correct
40 Correct 3282 ms 16488 KB Output is correct
41 Correct 3303 ms 17260 KB Output is correct
42 Correct 3368 ms 17432 KB Output is correct