oj.uz

Submission #868002

# Submission time Handle Problem Language Result Execution time Memory
868002 2023-10-30T07:31:03 Z HuyQuang_re_Zero Dancing Elephants (IOI11_elephants) C++14
100 / 100
 3105 ms 18276 KB 
#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

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.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8668 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 215 ms 9920 KB Output is correct
8 Correct 263 ms 10080 KB Output is correct
9 Correct 337 ms 11044 KB Output is correct
10 Correct 313 ms 10864 KB Output is correct
11 Correct 268 ms 10836 KB Output is correct
12 Correct 517 ms 10988 KB Output is correct
13 Correct 327 ms 10588 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8668 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 215 ms 9920 KB Output is correct
8 Correct 263 ms 10080 KB Output is correct
9 Correct 337 ms 11044 KB Output is correct
10 Correct 313 ms 10864 KB Output is correct
11 Correct 268 ms 10836 KB Output is correct
12 Correct 517 ms 10988 KB Output is correct
13 Correct 327 ms 10588 KB Output is correct
14 Correct 265 ms 10680 KB Output is correct
15 Correct 444 ms 10888 KB Output is correct
16 Correct 857 ms 11344 KB Output is correct
17 Correct 913 ms 12484 KB Output is correct
18 Correct 998 ms 12432 KB Output is correct
19 Correct 645 ms 12628 KB Output is correct
20 Correct 922 ms 12464 KB Output is correct
21 Correct 920 ms 12444 KB Output is correct
22 Correct 543 ms 12116 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8668 KB Output is correct
4 Correct 1 ms 8540 KB Output is correct
5 Correct 1 ms 8540 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 215 ms 9920 KB Output is correct
8 Correct 263 ms 10080 KB Output is correct
9 Correct 337 ms 11044 KB Output is correct
10 Correct 313 ms 10864 KB Output is correct
11 Correct 268 ms 10836 KB Output is correct
12 Correct 517 ms 10988 KB Output is correct
13 Correct 327 ms 10588 KB Output is correct
14 Correct 265 ms 10680 KB Output is correct
15 Correct 444 ms 10888 KB Output is correct
16 Correct 857 ms 11344 KB Output is correct
17 Correct 913 ms 12484 KB Output is correct
18 Correct 998 ms 12432 KB Output is correct
19 Correct 645 ms 12628 KB Output is correct
20 Correct 922 ms 12464 KB Output is correct
21 Correct 920 ms 12444 KB Output is correct
22 Correct 543 ms 12116 KB Output is correct
23 Correct 2492 ms 16180 KB Output is correct
24 Correct 2737 ms 16180 KB Output is correct
25 Correct 1985 ms 16180 KB Output is correct
26 Correct 2290 ms 16224 KB Output is correct
27 Correct 2379 ms 16216 KB Output is correct
28 Correct 457 ms 11860 KB Output is correct
29 Correct 426 ms 11724 KB Output is correct
30 Correct 461 ms 11720 KB Output is correct
31 Correct 427 ms 11604 KB Output is correct
32 Correct 1609 ms 15696 KB Output is correct
33 Correct 1474 ms 14976 KB Output is correct
34 Correct 1849 ms 16084 KB Output is correct
35 Correct 1455 ms 16316 KB Output is correct
36 Correct 1096 ms 15644 KB Output is correct
37 Correct 2507 ms 18276 KB Output is correct
38 Correct 1851 ms 14864 KB Output is correct
39 Correct 1947 ms 15696 KB Output is correct
40 Correct 1876 ms 14900 KB Output is correct
41 Correct 3046 ms 16064 KB Output is correct
42 Correct 3105 ms 15852 KB Output is correct