oj.uz

Submission #312487

# Submission time Handle Problem Language Result Execution time Memory
312487 2020-10-13T14:15:32 Z knon0501 Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 11980 KB 
#include <bits/stdc++.h>
using namespace std;
int t=400;
int n,L,m;
int b[150000];
int c[150000];
struct A{
    int x,cnt,nxt,idx;
};
vector<A> a[400];
int C;
void init(){
    int i,j;
    for(i=0 ; i<n ; i++)c[i]=b[i];
    sort(c,c+n);
    for(i=0 ; i<=(n-1)/t ; i++)a[i].clear();
    for(i=0 ; i<n  ;i++)
        a[i/t].push_back({c[i],0,0});
    for(i=(n-1)/t ; i>=0 ; i--){
        for(j=(int)a[i].size()-1 ; j>=0 ; j--){
            if(a[i][j].x+L>=a[i].rbegin()->x){
                a[i][j].nxt=a[i][j].x+L;
                a[i][j].cnt=1;
            }
            else{
                auto k=upper_bound(a[i].begin(),a[i].end(),(A){a[i][j].x+L,0,0},[&](A q,A w){
                        return q.x<w.x;
                        });
                a[i][j].cnt=k->cnt+1;
                a[i][j].nxt=k->nxt;
            }
        }
    }
}
void del(int x,int y){
    for(int i=0 ; i<a[x].size() ; i++){
        if(a[x][i].x==y){
            a[x].erase(a[x].begin()+i);
            break;
        }
    }
    for(int i=(int)a[x].size()-1 ; i>=0 ; i--){
        if(a[x][i].x+L>=a[x].rbegin()->x){
            a[x][i].nxt=a[x][i].x+L;
            a[x][i].cnt=1;
        }
        else{
            auto k=upper_bound(a[x].begin(),a[x].end(),(A){a[x][i].x+L,0,0},[&](A q,A w){
                        return q.x<w.x;
                        });
            a[x][i].cnt=k->cnt+1;
            a[x][i].nxt=k->nxt;
        }
    }
}
void add(int x,int y){
    for(int i=0 ; i<=a[x].size() ; i++){
        if(i==a[x].size() || a[x][i].x>=y ){
            a[x].insert(a[x].begin()+i,{y,0,0});
            break;
        }
    }

    for(int i=(int)a[x].size()-1 ; i>=0 ; i--){
        if(a[x][i].x+L>=a[x].rbegin()->x){
            a[x][i].nxt=a[x][i].x+L;
            a[x][i].cnt=1;
        }
        else{
            auto k=upper_bound(a[x].begin(),a[x].end(),(A){a[x][i].x+L,0,0},[&](A q,A w){
                        return q.x<w.x;
                        });
            a[x][i].cnt=k->cnt+1;
            a[x][i].nxt=k->nxt;
        }

     ///    cout<<C<<" "<<a[x][i].x<<" "<<a[x][i].nxt<<" "<<a[x][i].cnt<<endl;
    }
}
int f(){
    int x=-2e9;
    int ans=0;
    for(int i=0 ; i<=(n-1)/t ; i++){
        if(a[i].size()==0 || x>=a[i].rbegin()->x)continue;
        auto k=upper_bound(a[i].begin(),a[i].end(),(A){x,0,0},[&](A q, A w){
                           return q.x<w.x;
                           });
        ans+=k->cnt;
        x=k->nxt;
   ///     cout<<x<<" "<<ans<<"!\n";
    }
    return ans;
}
int g(int x){
    int k=-1;
    for(int i=0 ; i<=(n-1)/t ; i++){
        if (x<=a[i].rbegin()->x ){
        k=i;
        break;}
    }
    if(k>=0)return k;
    return (n-1)/t;
}/*
int main(){
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin>>n>>L>>m;
    int i;
    for(i=0 ; i<n ; i++)cin>>b[i];

    for(i=0 ; i<m ; i++)
    {
        if(i%(t-1)==0)init();

        int x,y;
        cin>>x>>y;
        del(g(b[x]),b[x]);
        add(g(y),y);
        b[x]=y;
        cout<<f()<<"\n";
    }
    return 0;
}*/
#include "elephants.h"



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

}

int update(int i, int y)
{
    if(C%(t-1)==0)init();
    C++;
    del(g(b[i]),b[i]);
    add(g(y),y);
    b[i]=y;
    return f();
}

Compilation message

elephants.cpp: In function 'void del(int, int)':
elephants.cpp:36:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<A>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |     for(int i=0 ; i<a[x].size() ; i++){
      |                   ~^~~~~~~~~~~~
elephants.cpp: In function 'void add(int, int)':
elephants.cpp:57:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<A>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   57 |     for(int i=0 ; i<=a[x].size() ; i++){
      |                   ~^~~~~~~~~~~~~
elephants.cpp:58:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<A>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |         if(i==a[x].size() || a[x][i].x>=y ){
      |            ~^~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1384 ms 1784 KB Output is correct
8 Correct 1386 ms 3064 KB Output is correct
9 Correct 1525 ms 4216 KB Output is correct
10 Correct 1594 ms 4092 KB Output is correct
11 Correct 1374 ms 3904 KB Output is correct
12 Correct 2268 ms 4088 KB Output is correct
13 Correct 1473 ms 3832 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1384 ms 1784 KB Output is correct
8 Correct 1386 ms 3064 KB Output is correct
9 Correct 1525 ms 4216 KB Output is correct
10 Correct 1594 ms 4092 KB Output is correct
11 Correct 1374 ms 3904 KB Output is correct
12 Correct 2268 ms 4088 KB Output is correct
13 Correct 1473 ms 3832 KB Output is correct
14 Correct 1168 ms 3644 KB Output is correct
15 Correct 1966 ms 3448 KB Output is correct
16 Correct 3309 ms 4648 KB Output is correct
17 Correct 3766 ms 5652 KB Output is correct
18 Correct 3745 ms 5496 KB Output is correct
19 Correct 2682 ms 5776 KB Output is correct
20 Correct 3760 ms 5624 KB Output is correct
21 Correct 3665 ms 5624 KB Output is correct
22 Correct 2364 ms 5112 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1384 ms 1784 KB Output is correct
8 Correct 1386 ms 3064 KB Output is correct
9 Correct 1525 ms 4216 KB Output is correct
10 Correct 1594 ms 4092 KB Output is correct
11 Correct 1374 ms 3904 KB Output is correct
12 Correct 2268 ms 4088 KB Output is correct
13 Correct 1473 ms 3832 KB Output is correct
14 Correct 1168 ms 3644 KB Output is correct
15 Correct 1966 ms 3448 KB Output is correct
16 Correct 3309 ms 4648 KB Output is correct
17 Correct 3766 ms 5652 KB Output is correct
18 Correct 3745 ms 5496 KB Output is correct
19 Correct 2682 ms 5776 KB Output is correct
20 Correct 3760 ms 5624 KB Output is correct
21 Correct 3665 ms 5624 KB Output is correct
22 Correct 2364 ms 5112 KB Output is correct
23 Execution timed out 9019 ms 11980 KB Time limit exceeded
24 Halted 0 ms 0 KB -