oj.uz

Submission #550088

# Submission time Handle Problem Language Result Execution time Memory
550088 2022-04-17T08:26:02 Z neki Dancing Elephants (IOI11_elephants) C++14
100 / 100
 7850 ms 16684 KB 
#include <bits/stdc++.h>

using namespace std;

#define vc vector
#define ps push_back

const int mm=350;
int n, l;

struct e{
    int i, pos, val, odsek, kok;
    
    e(int i_, int pos_): i(i_), pos(pos_){}
    
    bool operator<(const e& oth){return pos < oth.pos;}
};
vc<e> es;

vc<vc<e*>> dp;

void calcdp(vc<e*>& arr){
    int siz=arr.size(), nas=siz;
    if(siz==0) return;
    for(int i=siz-1;i>=0;--i){
        while((*arr[i]).pos+l<= (*arr[nas-1]).pos) --nas;
        if(nas<siz) (*arr[i]).val=(*arr[nas]).val, (*arr[i]).kok=(*arr[nas]).kok + 1;
        else (*arr[i]).val=(*arr[i]).pos+l, (*arr[i]).kok=1;
    }
}

void build(){
    vc<e*> vsi;
    for(auto v : dp) for(auto u : v ) vsi.push_back(u);
    
    dp.clear();
    for(int ods=0;ods<n;ods+=mm){
        vc<e*> nods;
        for(int i=ods;i<min(n, ods+mm);++i){(*vsi[i]).odsek=ods/mm;nods.ps(vsi[i]);}
        calcdp(nods);
        dp.ps(nods);
    }
}

void init(int N, int L, int* X){
    n=N, l=L+1;
    
    for(int i=0;i<n;++i) es.ps(e(i, X[i]));
    dp.ps({});
    for(int i=0;i<n;++i)dp[0].ps(&es[i]);
    build();
}

int cnt=0;
int update(int ind, int y){
    int nov=dp.size()-1; for(int i=0;i<dp.size();++i) if(dp[i].size()>0 and y<=(*(dp[i].back())).pos){nov=i;break;}    
    int star = es[ind].odsek;
    
    es[ind].pos=y;
    if(nov!=star){
    	es[ind].odsek=nov;
    	
        vc<e*> shrani=dp[star];
        dp[star].clear();
        for(auto v : shrani) if((*v).i != ind) dp[star].ps(v);
        calcdp(dp[star]);
        
        dp[nov].ps(&es[ind]);
    }
    
    sort(dp[nov].begin(), dp[nov].end(), [](e* a, e* b){return (*a)<(*b);});
    calcdp(dp[nov]);
    
    ++cnt;if(cnt%mm==0) build();
    
    int curpos=-1, ret=0;
    for(auto&& v: dp) if(v.size()>0 and curpos<=(*(v.back())).pos){
        int L=0, R=v.size()-1; //nani
        while(L<R){
            int mid=(L+R)/2;
            if(curpos <= (*v[mid]).pos) R=mid;
            else L=mid+1;
        }
        
        curpos= (*v[L]).val;
        ret+= (*v[L]).kok;
    }
    
    return ret;
}

Compilation message

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:56:39: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<e*> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |     int nov=dp.size()-1; for(int i=0;i<dp.size();++i) if(dp[i].size()>0 and y<=(*(dp[i].back())).pos){nov=i;break;}
      |                                      ~^~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 910 ms 1676 KB Output is correct
8 Correct 1796 ms 1996 KB Output is correct
9 Correct 445 ms 3768 KB Output is correct
10 Correct 606 ms 3848 KB Output is correct
11 Correct 615 ms 5092 KB Output is correct
12 Correct 1213 ms 5512 KB Output is correct
13 Correct 639 ms 4936 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 910 ms 1676 KB Output is correct
8 Correct 1796 ms 1996 KB Output is correct
9 Correct 445 ms 3768 KB Output is correct
10 Correct 606 ms 3848 KB Output is correct
11 Correct 615 ms 5092 KB Output is correct
12 Correct 1213 ms 5512 KB Output is correct
13 Correct 639 ms 4936 KB Output is correct
14 Correct 845 ms 3840 KB Output is correct
15 Correct 579 ms 3936 KB Output is correct
16 Correct 1984 ms 5832 KB Output is correct
17 Correct 1892 ms 7736 KB Output is correct
18 Correct 2025 ms 7548 KB Output is correct
19 Correct 2812 ms 7752 KB Output is correct
20 Correct 1918 ms 7616 KB Output is correct
21 Correct 1969 ms 7656 KB Output is correct
22 Correct 1128 ms 7220 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 910 ms 1676 KB Output is correct
8 Correct 1796 ms 1996 KB Output is correct
9 Correct 445 ms 3768 KB Output is correct
10 Correct 606 ms 3848 KB Output is correct
11 Correct 615 ms 5092 KB Output is correct
12 Correct 1213 ms 5512 KB Output is correct
13 Correct 639 ms 4936 KB Output is correct
14 Correct 845 ms 3840 KB Output is correct
15 Correct 579 ms 3936 KB Output is correct
16 Correct 1984 ms 5832 KB Output is correct
17 Correct 1892 ms 7736 KB Output is correct
18 Correct 2025 ms 7548 KB Output is correct
19 Correct 2812 ms 7752 KB Output is correct
20 Correct 1918 ms 7616 KB Output is correct
21 Correct 1969 ms 7656 KB Output is correct
22 Correct 1128 ms 7220 KB Output is correct
23 Correct 3473 ms 16536 KB Output is correct
24 Correct 3491 ms 16548 KB Output is correct
25 Correct 3056 ms 16684 KB Output is correct
26 Correct 4186 ms 16552 KB Output is correct
27 Correct 7806 ms 16360 KB Output is correct
28 Correct 2567 ms 5480 KB Output is correct
29 Correct 2556 ms 5496 KB Output is correct
30 Correct 2574 ms 5336 KB Output is correct
31 Correct 2506 ms 5468 KB Output is correct
32 Correct 3145 ms 16004 KB Output is correct
33 Correct 2620 ms 15316 KB Output is correct
34 Correct 3708 ms 16344 KB Output is correct
35 Correct 2953 ms 16424 KB Output is correct
36 Correct 2511 ms 15932 KB Output is correct
37 Correct 5516 ms 16392 KB Output is correct
38 Correct 3966 ms 15244 KB Output is correct
39 Correct 7850 ms 16188 KB Output is correct
40 Correct 5016 ms 15204 KB Output is correct
41 Correct 6844 ms 16056 KB Output is correct
42 Correct 6672 ms 16144 KB Output is correct