oj.uz

Submission #821673

# Submission time Handle Problem Language Result Execution time Memory
821673 2023-08-11T12:52:50 Z annabeth9680 Dancing Elephants (IOI11_elephants) C++17
100 / 100
 7641 ms 16640 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2e5+5;
const int INF = 1e9+5;
int arr[MAXN],n,l,pos[MAXN]; //bucket i is in
bool cmp(int x, int y){
    return arr[x]<arr[y];
}
struct bucket{
    vector<vector<int>> vec,nxt,fotos;
    void build(){
      	vec.clear(); nxt.clear(); fotos.clear();
        vector<int> ind;
        for(int i = 1;i<=n;++i) ind.push_back(i);
        sort(ind.begin(),ind.end(),cmp);
        int id = 0, b = 0;
        while(id < n){
            b++;
            if(b == 1) vec.push_back({});
            vec.back().push_back(ind[id]);
            pos[ind[id]] = vec.size()-1;
            id++;
            if(b >= 500) b = 0;
        }
        for(int i = 0;i<vec.size();++i){
            vector<int> v(2505);
            fotos.push_back(v); nxt.push_back(v);
            int cur = vec[i].size()-1;
            for(int j = vec[i].size()-1;j >= 0;--j){
                while(cur > 0 && arr[vec[i][cur-1]] > arr[vec[i][j]]+l) cur--;
                if(arr[vec[i][cur]] <= arr[vec[i][j]]+l){
                    fotos[i][j] = 1;
                    nxt[i][j] = arr[vec[i][j]]+l+1;
                }
                else{
                    fotos[i][j] = fotos[i][cur]+1;
                    nxt[i][j] = nxt[i][cur];
                }
            }
        }
    }
    int query(){
        int lo = -INF, ans = 0;
        for(int i = 0;i<vec.size();++i){ //find the first position that is >= lo
            int l = 0, r = vec[i].size()-1, erg = -1;
            while(l <= r){
                int mid = (l+r)/2;
                if(arr[vec[i][mid]] >= lo){
                    erg = mid;
                    r = mid-1;
                }
                else{
                    l = mid+1;
                }
            }
            if(erg == -1) continue;
            ans += fotos[i][erg]; lo = nxt[i][erg];
        }
        return ans;
    }
    void ins(int id){
        int bnum = 0;
        for(int i = vec.size()-1;i>=0;--i){
            if(arr[vec[i][0]] <= arr[id]){
                bnum = i;
                break;
            }
        }
        bool good = false;
        for(int i = 0;i<vec[bnum].size();++i){
            if(arr[vec[bnum][i]] > arr[id]){
                vec[bnum].insert(vec[bnum].begin()+i,id);
                good = true;
                break;
            }
        }
        pos[id] = bnum;
        if(!good) vec[bnum].push_back(id);
        int i = bnum;
        int cur = vec[i].size()-1;
        for(int j = vec[i].size()-1;j >= 0;--j){
            while(cur > 0 && arr[vec[i][cur-1]] > arr[vec[i][j]]+l) cur--;
            if(arr[vec[i][cur]] <= arr[vec[i][j]]+l){
                fotos[i][j] = 1;
                nxt[i][j] = arr[vec[i][j]]+l+1;
            }
            else{
                fotos[i][j] = fotos[i][cur]+1;
                nxt[i][j] = nxt[i][cur];
            }
        }
    }
    void del(int id){
        int bnum = pos[id];
        for(int i = 0;i<vec[bnum].size();++i){
            if(vec[bnum][i] == id){
                vec[bnum].erase(vec[bnum].begin()+i);
                break;
            }
        }
        int i = bnum;
        int cur = vec[i].size()-1;
        for(int j = vec[i].size()-1;j >= 0;--j){
            while(cur > 0 && arr[vec[i][cur-1]] > arr[vec[i][j]]+l) cur--;
            if(arr[vec[i][cur]] <= arr[vec[i][j]]+l){
                fotos[i][j] = 1;
                nxt[i][j] = arr[vec[i][j]]+l+1;
            }
            else{
                fotos[i][j] = fotos[i][cur]+1;
                nxt[i][j] = nxt[i][cur];
            }
        }
    }
};
int curq; bucket eimer;
void init(int N, int L, int X[]){
    n = N; l = L;
    for(int i = 1;i<=N;++i) arr[i] = X[i-1];
    eimer.build();
    curq = 490;
}
int update(int i, int y){
    arr[i+1] = y;
    curq--;
    if(curq == 0){
        eimer.build();
        curq = 490;
    }
    else{
        eimer.del(i+1);
        arr[i+1] = y;
        eimer.ins(i+1);
    }
    return eimer.query();
}

Compilation message

elephants.cpp: In member function 'void bucket::build()':
elephants.cpp:26:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   26 |         for(int i = 0;i<vec.size();++i){
      |                       ~^~~~~~~~~~~
elephants.cpp: In member function 'int bucket::query()':
elephants.cpp:45:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 |         for(int i = 0;i<vec.size();++i){ //find the first position that is >= lo
      |                       ~^~~~~~~~~~~
elephants.cpp: In member function 'void bucket::ins(int)':
elephants.cpp:71:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   71 |         for(int i = 0;i<vec[bnum].size();++i){
      |                       ~^~~~~~~~~~~~~~~~~
elephants.cpp: In member function 'void bucket::del(int)':
elephants.cpp:96:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   96 |         for(int i = 0;i<vec[bnum].size();++i){
      |                       ~^~~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 308 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 0 ms 340 KB Output is correct
3 Correct 0 ms 308 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 308 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 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 308 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 327 ms 2600 KB Output is correct
8 Correct 351 ms 3044 KB Output is correct
9 Correct 545 ms 5552 KB Output is correct
10 Correct 682 ms 5452 KB Output is correct
11 Correct 711 ms 5340 KB Output is correct
12 Correct 970 ms 5388 KB Output is correct
13 Correct 689 ms 5076 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 308 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 327 ms 2600 KB Output is correct
8 Correct 351 ms 3044 KB Output is correct
9 Correct 545 ms 5552 KB Output is correct
10 Correct 682 ms 5452 KB Output is correct
11 Correct 711 ms 5340 KB Output is correct
12 Correct 970 ms 5388 KB Output is correct
13 Correct 689 ms 5076 KB Output is correct
14 Correct 444 ms 3780 KB Output is correct
15 Correct 596 ms 4112 KB Output is correct
16 Correct 1579 ms 6096 KB Output is correct
17 Correct 1783 ms 7604 KB Output is correct
18 Correct 1868 ms 7516 KB Output is correct
19 Correct 1300 ms 7728 KB Output is correct
20 Correct 1861 ms 7588 KB Output is correct
21 Correct 1799 ms 7560 KB Output is correct
22 Correct 1373 ms 7152 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 308 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 308 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 327 ms 2600 KB Output is correct
8 Correct 351 ms 3044 KB Output is correct
9 Correct 545 ms 5552 KB Output is correct
10 Correct 682 ms 5452 KB Output is correct
11 Correct 711 ms 5340 KB Output is correct
12 Correct 970 ms 5388 KB Output is correct
13 Correct 689 ms 5076 KB Output is correct
14 Correct 444 ms 3780 KB Output is correct
15 Correct 596 ms 4112 KB Output is correct
16 Correct 1579 ms 6096 KB Output is correct
17 Correct 1783 ms 7604 KB Output is correct
18 Correct 1868 ms 7516 KB Output is correct
19 Correct 1300 ms 7728 KB Output is correct
20 Correct 1861 ms 7588 KB Output is correct
21 Correct 1799 ms 7560 KB Output is correct
22 Correct 1373 ms 7152 KB Output is correct
23 Correct 4601 ms 16452 KB Output is correct
24 Correct 4757 ms 16640 KB Output is correct
25 Correct 4037 ms 16460 KB Output is correct
26 Correct 5631 ms 16456 KB Output is correct
27 Correct 6209 ms 16308 KB Output is correct
28 Correct 1536 ms 5332 KB Output is correct
29 Correct 1468 ms 5444 KB Output is correct
30 Correct 1571 ms 5648 KB Output is correct
31 Correct 1464 ms 5412 KB Output is correct
32 Correct 5348 ms 15884 KB Output is correct
33 Correct 5370 ms 15216 KB Output is correct
34 Correct 5330 ms 16092 KB Output is correct
35 Correct 4439 ms 16392 KB Output is correct
36 Correct 3015 ms 15876 KB Output is correct
37 Correct 6933 ms 16280 KB Output is correct
38 Correct 5421 ms 15120 KB Output is correct
39 Correct 5993 ms 16128 KB Output is correct
40 Correct 5444 ms 15116 KB Output is correct
41 Correct 7641 ms 15876 KB Output is correct
42 Correct 7371 ms 16172 KB Output is correct