Submission #312474

#	Time	Username	Problem	Language	Result	Execution time	Memory
312474		knon0501	Dancing Elephants (IOI11_elephants)	C++14	0 / 100	1 ms	384 KiB

elephants

#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];

void init(){
    int i,j;
    for(i=0 ; i<n ; i++)c[i]=b[i];
    sort(c,c+n);
    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<<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;
    }
    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;
    }
    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"


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

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

Compilation message (stderr)

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

• Subtask 1: 0 / 10
• Subtask 2: 0 / 16
• Subtask 3: 0 / 24
• Subtask 4: 0 / 47
• Subtask 5: 0 / 3