Submission #868002

#	Time	Username	Problem	Language	Result	Execution time	Memory
868002		HuyQuang_re_Zero	Dancing Elephants (IOI11_elephants)	C++14	100 / 100	3105 ms	18276 KiB

elephants

#include <bits/stdc++.h>
#define ll long long
#define db long double
#define II pair <ll,ll>
#define III pair <ll,II>
#define IV pair <vector <int>,vector <int> >
#define fst first
#define snd second
#define BIT(x,i) ((x>>i)&1)
#define pi acos(-1)
#define to_radian(x) (x*pi/180.0)
#define to_degree(x) (x*180.0/pi)
#define Log(x) (31-__builtin_clz((int)x))
#define LogLL(x) (63-__builtin_clzll((ll)x))
#define mxn 150005
#include "elephants.h"
using namespace std;
struct International_Olympiad_in_Informatics
{
    struct Block
    {
        int sz=0,L;
        vector <int> x,seg,mx_pos;
        void Init()
        {
            sz=0;
            x.clear(); x.push_back(0);
            seg.clear(); seg.push_back(0);
            mx_pos.clear(); mx_pos.push_back(0);
        }
        void Push_back(int k)
        {
            sz++;
            x.push_back(k);
            seg.push_back(0);
            mx_pos.push_back(0);
        }
        void Cal()
        {
            int j=sz;
            for(int i=sz;i>=1;i--)
            {
                while(x[j]-x[i]>L) j--;
                if(j==sz) seg[i]=1,mx_pos[i]=x[i]+L;
                else seg[i]=seg[j+1]+1,mx_pos[i]=mx_pos[j+1];
            }
        }
        void Add(int k)
        {
            vector <int> tg=x;
            Init();
            for(int i=1;i<tg.size();i++)
                if(tg[i]<=k) Push_back(tg[i]);
            Push_back(k);
            for(int i=1;i<tg.size();i++)
                if(tg[i]>k) Push_back(tg[i]);
            Cal();
        }
        void Del(int k)
        {
            vector <int> tg=x;
            Init();
            int pos;
            for(int i=1;i<tg.size();i++)
                if(tg[i]==k) { pos=i; break; }
            for(int i=1;i<pos;i++) Push_back(tg[i]);
            for(int i=pos+1;i<tg.size();i++) Push_back(tg[i]);
            Cal();
        }
    } B[401];


    int n,n_block,i,j,x[mxn],root,n_update,val[mxn];
    void Build_block_from_val()
    {
        n_block=0;
      //  cerr<<n<<'\n';
        for(i=1;i<=n;i++)
        {
            if(i==1 || B[n_block].sz==root) B[++n_block].Init();
            B[n_block].Push_back(val[i]);
        }
        for(i=1;i<=n_block;i++) B[i].Cal();
    }
    void Init(int _n,int _l,int _x[])
    {
        n=_n;
        root=trunc(sqrt(n));
        for(i=1;i<=n;i++) x[i]=val[i]=_x[i];
        for(i=1;i<=400;i++) B[i].L=_l;
        //////////////////////////////////
        Build_block_from_val();
    }
    int update(int u,int k)
    {
        for(i=1;i<=n_block;i++)
            if(B[i].sz>0 && B[i].x[B[i].sz]>=x[u]) break;
        B[i].Del(x[u]);
        x[u]=k;
        int ma=0;
        for(i=1;i<=n_block;i++)
        {
            ma=max(ma,B[i].x[B[i].sz]);
            if(i==n_block || ma>x[u]) break;
        }
        B[i].Add(x[u]);
        if(++n_update==root)
        {
            n=0;
            for(i=1;i<=n_block;i++)
                for(j=1;j<=B[i].sz;j++) val[++n]=B[i].x[j];
          //  if(B[2].sz>1) cerr<<B[2].x[1]<<" "<<B[2].x[2]<<'\n';
           // cout<<B[1].sz<<" "<<B[2].sz<<'\n';
            //cout<<n<<'\n';
            Build_block_from_val();
            n_update=0;
        }

        int mx_pos=-1,res=0;
        for(i=1;i<=n_block;i++)
        {
            if(B[i].sz==0 || mx_pos>=B[i].x.back()) continue;
            int l=0,r=B[i].sz;
            while(l<r)
            {
                int mid=(l+r+1)>>1;
                if(B[i].x[mid]<=mx_pos) l=mid; else r=mid-1;
            }
            res+=B[i].seg[l+1];
            mx_pos=B[i].mx_pos[l+1];
        }
        return res;
    }
} IOI;



void init(int n,int l,int x[])
{
    for(int i=n;i>=1;i--) x[i]=x[i-1];
    IOI.Init(n,l,x);
}
int update(int i,int y)
{
    i++;
    return IOI.update(i,y);
}
/*
Write the following procedures:
• Procedure init(N,L,X) that takes the following parameters:
• N – the number of elephants. The elephants are numbered 0 through N-1.
• L – the length of the segment captured by a single camera. You may assume
that L is an integer such that 0 ≤ L ≤ 1 000 000 000.
• X – a one-dimensional array of integers representing the initial positions of the
elephants. For 0 ≤ i < N, elephant i starts at the position X[i]. The initial
positions are in sorted order. More precisely, you may assume that
0 ≤ X[0] ≤ ... ≤ X[N-1] ≤ 1 000 000 000. Note that during the dance the
elephants may reorder themselves.
This procedure will be called only once, prior to all calls to update. It does not return any
value.
• Procedure update(i,y) that takes the following parameters:
• i – the number of the elephant that moves in the current act.
• y – the position where the elephant i will stand after the current act. You may assume that y is an integer such that 0 ≤ y ≤ 1 000 000 000.
This procedure will be called multiple times. Each call corresponds to a single act (which
follows on from all of the previous acts). Each call must return the minimum number of
cameras needed to photograph all elephants after the corresponding act
*/
/*
int n,l,i,x[mxn],y,k,q;
int main()
{
    freopen("elephants.inp","r",stdin);
    freopen("elephants.out","w",stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin>>n>>l>>q;
    for(i=0;i<n;i++) cin>>x[i];
    init(n,l,x);
    while(cin>>i>>y>>k) cout<<update(i,y)<<'\n';
}

*/

Compilation message (stderr)

elephants.cpp: In member function 'void International_Olympiad_in_Informatics::Block::Add(int)':
elephants.cpp:52:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   52 |             for(int i=1;i<tg.size();i++)
      |                         ~^~~~~~~~~~
elephants.cpp:55:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   55 |             for(int i=1;i<tg.size();i++)
      |                         ~^~~~~~~~~~
elephants.cpp: In member function 'void International_Olympiad_in_Informatics::Block::Del(int)':
elephants.cpp:64:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |             for(int i=1;i<tg.size();i++)
      |                         ~^~~~~~~~~~
elephants.cpp:67:30: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   67 |             for(int i=pos+1;i<tg.size();i++) Push_back(tg[i]);
      |                             ~^~~~~~~~~~
elephants.cpp:63:17: warning: 'pos' may be used uninitialized in this function [-Wmaybe-uninitialized]
   63 |             int pos;
      |                 ^~~

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