oj.uz

Submission #1028604

# Submission time Handle Problem Language Result Execution time Memory
1028604 2024-07-20T05:56:22 Z ngrace Dancing Elephants (IOI11_elephants) C++14
100 / 100
 6538 ms 27552 KB 
#include <bits/stdc++.h>
#include "elephants.h"
using namespace std;
#define v vector
#define ii pair<int,int>
#define fi first
#define se second

const int MAXN = 150000;
int N, L;
v<int> E;


void init(int n, int l, int X[])
{
    N = n;
    L = l;
    for(int i=0; i<N; i++) E.push_back(X[i]);
}

const int BUCK = 400;
int qNum = 0;
v<int> buckInd(MAXN);
v<v<ii>> bucks(MAXN/BUCK + 1);
v<v<ii>> bucksAns(MAXN/BUCK+1);

void rebuildBuck(int b){
    bucksAns[b].resize(bucks[b].size(), {0,0});
    for(int i=bucks[b].size()-1; i>=0; i--){
        auto it = lower_bound(bucks[b].begin()+i+1, bucks[b].end(), make_pair(bucks[b][i].fi+L+1, -1));
        if(it==bucks[b].end()) bucksAns[b][i] = {1, bucks[b][i].fi+L+1};
        else{
            ii tmp = bucksAns[b][distance(bucks[b].begin(), it)];
            bucksAns[b][i] = {1 + tmp.fi, tmp.se};
        }
    }
}

void rebuild(){
    v<ii> e;
    for(int i=0; i<N; i++) e.push_back({E[i], i});
    sort(e.begin(), e.end());
    for(int i=0; i<bucks.size(); i++) bucks[i].clear();
    int b=0;
    for(auto it:e){
        if(bucks[b].size()==BUCK) b++;
        bucks[b].push_back(it);
        buckInd[it.se] = b;
    }
    for(int i=0; i<bucks.size(); i++) rebuildBuck(i);
}

void move(int e, int x){
    int b = buckInd[e];
    bucks[b].erase(find(bucks[b].begin(), bucks[b].end(), make_pair(E[e], e)));
    rebuildBuck(b);
    E[e] = x;
    int l=0, r=bucks.size()-1;
    while(l<r){
        int m=(l+r+1)/2;
        if(bucks[m].size()>0 && bucks[m][0].fi<=x) l=m;
        else r=m-1;
    }
    auto it = upper_bound(bucks[l].begin(), bucks[l].end(), make_pair(x, e));
    bucks[l].insert(it, {x, e});
    buckInd[e] = l;
    rebuildBuck(l);
}

int ans(){
    int cur = 0;
    int ret = 0;
    for(int b=0; b<bucks.size(); b++){
        auto it = lower_bound(bucks[b].begin(), bucks[b].end(), make_pair(cur, -1));
        if(it!=bucks[b].end()){
            int i = distance(bucks[b].begin(), it);
            ret += bucksAns[b][i].fi;
            cur = bucksAns[b][i].se;
        }
    }
    return ret;
}

void debug(int b){
    for(int i=0; i<bucks[b].size(); i++) cout<<bucks[b][i].fi<<" "<<bucks[b][i].se<<" "<<bucksAns[b][i].fi<<" "<<bucksAns[b][i].se<<endl;
    cout<<endl;
}

int update(int i, int y){
    if((qNum++)%BUCK==0) rebuild();
    move(i, y);
    return ans();
}

Compilation message

elephants.cpp: In function 'void rebuild()':
elephants.cpp:43:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   43 |     for(int i=0; i<bucks.size(); i++) bucks[i].clear();
      |                  ~^~~~~~~~~~~~~
elephants.cpp:50:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int i=0; i<bucks.size(); i++) rebuildBuck(i);
      |                  ~^~~~~~~~~~~~~
elephants.cpp: In function 'int ans()':
elephants.cpp:73:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<std::pair<int, int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for(int b=0; b<bucks.size(); b++){
      |                  ~^~~~~~~~~~~~~
elephants.cpp: In function 'void debug(int)':
elephants.cpp:85: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]
   85 |     for(int i=0; i<bucks[b].size(); i++) cout<<bucks[b][i].fi<<" "<<bucks[b][i].se<<" "<<bucksAns[b][i].fi<<" "<<bucksAns[b][i].se<<endl;
      |                  ~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7004 KB Output is correct
2 Correct 1 ms 7004 KB Output is correct
3 Correct 1 ms 7004 KB Output is correct
4 Correct 1 ms 7004 KB Output is correct
5 Correct 1 ms 7004 KB Output is correct
6 Correct 1 ms 7004 KB Output is correct
7 Correct 568 ms 10932 KB Output is correct
8 Correct 558 ms 11348 KB Output is correct
9 Correct 586 ms 13144 KB Output is correct
10 Correct 730 ms 12932 KB Output is correct
11 Correct 637 ms 12484 KB Output is correct
12 Correct 1034 ms 13464 KB Output is correct
13 Correct 806 ms 12784 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7004 KB Output is correct
2 Correct 1 ms 7004 KB Output is correct
3 Correct 1 ms 7004 KB Output is correct
4 Correct 1 ms 7004 KB Output is correct
5 Correct 1 ms 7004 KB Output is correct
6 Correct 1 ms 7004 KB Output is correct
7 Correct 568 ms 10932 KB Output is correct
8 Correct 558 ms 11348 KB Output is correct
9 Correct 586 ms 13144 KB Output is correct
10 Correct 730 ms 12932 KB Output is correct
11 Correct 637 ms 12484 KB Output is correct
12 Correct 1034 ms 13464 KB Output is correct
13 Correct 806 ms 12784 KB Output is correct
14 Correct 732 ms 12184 KB Output is correct
15 Correct 832 ms 11960 KB Output is correct
16 Correct 1505 ms 13700 KB Output is correct
17 Correct 1774 ms 15204 KB Output is correct
18 Correct 1904 ms 15128 KB Output is correct
19 Correct 1179 ms 14728 KB Output is correct
20 Correct 1701 ms 15212 KB Output is correct
21 Correct 1706 ms 15172 KB Output is correct
22 Correct 1302 ms 14376 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 7004 KB Output is correct
2 Correct 1 ms 7004 KB Output is correct
3 Correct 1 ms 7004 KB Output is correct
4 Correct 1 ms 7004 KB Output is correct
5 Correct 1 ms 7004 KB Output is correct
6 Correct 1 ms 7004 KB Output is correct
7 Correct 568 ms 10932 KB Output is correct
8 Correct 558 ms 11348 KB Output is correct
9 Correct 586 ms 13144 KB Output is correct
10 Correct 730 ms 12932 KB Output is correct
11 Correct 637 ms 12484 KB Output is correct
12 Correct 1034 ms 13464 KB Output is correct
13 Correct 806 ms 12784 KB Output is correct
14 Correct 732 ms 12184 KB Output is correct
15 Correct 832 ms 11960 KB Output is correct
16 Correct 1505 ms 13700 KB Output is correct
17 Correct 1774 ms 15204 KB Output is correct
18 Correct 1904 ms 15128 KB Output is correct
19 Correct 1179 ms 14728 KB Output is correct
20 Correct 1701 ms 15212 KB Output is correct
21 Correct 1706 ms 15172 KB Output is correct
22 Correct 1302 ms 14376 KB Output is correct
23 Correct 3848 ms 26348 KB Output is correct
24 Correct 4094 ms 26388 KB Output is correct
25 Correct 2990 ms 25876 KB Output is correct
26 Correct 4535 ms 25092 KB Output is correct
27 Correct 4963 ms 24944 KB Output is correct
28 Correct 1784 ms 16724 KB Output is correct
29 Correct 1800 ms 16740 KB Output is correct
30 Correct 1777 ms 16472 KB Output is correct
31 Correct 1831 ms 16744 KB Output is correct
32 Correct 3831 ms 24776 KB Output is correct
33 Correct 3982 ms 23864 KB Output is correct
34 Correct 4242 ms 25028 KB Output is correct
35 Correct 3950 ms 25124 KB Output is correct
36 Correct 3833 ms 24528 KB Output is correct
37 Correct 6538 ms 27552 KB Output is correct
38 Correct 4555 ms 23868 KB Output is correct
39 Correct 4222 ms 24776 KB Output is correct
40 Correct 4464 ms 24012 KB Output is correct
41 Correct 6175 ms 25828 KB Output is correct
42 Correct 6326 ms 26204 KB Output is correct