oj.uz

Submission #465411

# Submission time Handle Problem Language Result Execution time Memory
465411 2021-08-16T00:41:47 Z JovanB Dancing Elephants (IOI11_elephants) C++17
50 / 100
 9000 ms 8016 KB 
#pragma GCC optimize("Ofast")
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;

int n, k;

const int N = 150000;
const int K = 250;

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; 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; 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:19: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]
   19 |         if(j == vec[tr].size() - 1){
      |            ~~^~~~~~~~~~~~~~~~~~~~~
elephants.cpp: In function 'void brisi(int, int)':
elephants.cpp:71: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]
   71 |     for(int i=0; i<vec[tr].size(); i++){
      |                  ~^~~~~~~~~~~~~~~
elephants.cpp: In function 'void dodaj(int, int)':
elephants.cpp:80: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]
   80 |     for(int i=0; i<vec[tr].size(); i++){
      |                  ~^~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3788 KB Output is correct
2 Correct 3 ms 3788 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 3 ms 3788 KB Output is correct
2 Correct 3 ms 3788 KB Output is correct
3 Correct 3 ms 3788 KB Output is correct
4 Correct 3 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 3 ms 3788 KB Output is correct
2 Correct 3 ms 3788 KB Output is correct
3 Correct 3 ms 3788 KB Output is correct
4 Correct 3 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 1989 ms 6016 KB Output is correct
8 Correct 2660 ms 6536 KB Output is correct
9 Correct 6910 ms 7484 KB Output is correct
10 Correct 7028 ms 7916 KB Output is correct
11 Correct 7070 ms 7800 KB Output is correct
12 Correct 7034 ms 8004 KB Output is correct
13 Correct 7053 ms 7712 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3788 KB Output is correct
2 Correct 3 ms 3788 KB Output is correct
3 Correct 3 ms 3788 KB Output is correct
4 Correct 3 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 1989 ms 6016 KB Output is correct
8 Correct 2660 ms 6536 KB Output is correct
9 Correct 6910 ms 7484 KB Output is correct
10 Correct 7028 ms 7916 KB Output is correct
11 Correct 7070 ms 7800 KB Output is correct
12 Correct 7034 ms 8004 KB Output is correct
13 Correct 7053 ms 7712 KB Output is correct
14 Correct 3742 ms 7092 KB Output is correct
15 Correct 4646 ms 7036 KB Output is correct
16 Execution timed out 9086 ms 8016 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 3788 KB Output is correct
2 Correct 3 ms 3788 KB Output is correct
3 Correct 3 ms 3788 KB Output is correct
4 Correct 3 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 1989 ms 6016 KB Output is correct
8 Correct 2660 ms 6536 KB Output is correct
9 Correct 6910 ms 7484 KB Output is correct
10 Correct 7028 ms 7916 KB Output is correct
11 Correct 7070 ms 7800 KB Output is correct
12 Correct 7034 ms 8004 KB Output is correct
13 Correct 7053 ms 7712 KB Output is correct
14 Correct 3742 ms 7092 KB Output is correct
15 Correct 4646 ms 7036 KB Output is correct
16 Execution timed out 9086 ms 8016 KB Time limit exceeded
17 Halted 0 ms 0 KB -