oj.uz

Submission #90423

# Submission time Handle Problem Language Result Execution time Memory
90423 2018-12-21T15:42:44 Z Bodo171 Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 88932 KB 
#include "elephants.h"
#include <iostream>
const int nmax=150005;
const int buck=800;
const int B=3200;
using namespace std;
pair<int,int> dp[B][B],b[B][B];
pair<int,int> unde[nmax],v[nmax];
int lg[nmax];
int sz[B];
int n,m,i,j,L,bucks,actbucks;
void baga(int wh,int x,int poz)
{
    sz[wh]++;
    for(int p=sz[wh];p>=1;p--)
    {
        if(b[wh][p-1].first<=x)
        {
            b[wh][p]={x,poz};
            unde[poz]={wh,p};
            return;
        }
        b[wh][p]=b[wh][p-1];
        unde[b[wh][p].second]={wh,p};
    }
}
int cb(int wh,int val)
{
    //resturneaza pozitia primului element mai mare ca val din bucketul wh
    int ret=0;
    for(int p=lg[sz[wh]];p>=0;p--)
        if(ret+(1<<p)<=sz[wh]&&b[wh][ret+(1<<p)].first<=val)
          ret+=(1<<p);
    ret++;
    return ret;
}
void recalc(int wh)
{
    int poz=0;
    b[wh][sz[wh]+1].first=2*1000*1000*1000+5;poz=sz[wh]+1;
    for(int i=sz[wh];i>=1;i--)
    {
        while(b[wh][poz].first>b[wh][i].first+L)
           poz--;
        if(b[wh][i].first+L>=b[wh][poz].first)
            poz++;
        if(poz<=sz[wh])
        {
            dp[wh][i]=dp[wh][poz];
            dp[wh][i].first++;
        }
        else
        {
            dp[wh][i]={1,b[wh][i].first+L};
        }
    }
}
void sterge(int wh,int pp)
{
    for(int p=pp;p<sz[wh];p++)
    {
        unde[b[wh][p+1].second]={wh,p};
        b[wh][p]=b[wh][p+1];
    }
    sz[wh]--;
    recalc(wh);
    return;
}

void ins(int poz,int x)
{
    int wh=0;
    for(int i=1;i<=actbucks&&wh==0;i++)
    {
        if(b[i][sz[i]].first>=x)
        {
            baga(i,x,poz);
            wh=i;
        }
    }
    if(wh==0)
    {
        actbucks++;
        wh=actbucks;
        baga(wh,x,poz);
    }
    recalc(wh);
}
int rec_all()
{
    int ret=0,act=0,poz;
    for(int i=1;i<=bucks;i++)
        if(sz[i])
    {
        if(ret==0)
        {
            act=dp[i][1].second;
            ret=dp[i][1].first;
        }
        else
        {
            poz=cb(i,act);
            if(poz<=sz[i])
            {
                ret+=dp[i][poz].first;
                act=dp[i][poz].second;
            }
        }
    }
    return ret;
}
void rebucket()
{
    bucks=(n/buck+1)+buck;int nr=1;
    actbucks=0;
    for(int i=1;i<=bucks;i++)
    {
       sz[i]=0;
       for(j=nr;j<=min(nr+buck-1,n);j++)
        {
            baga(i,v[j].first,v[j].second);
        }
        if(nr<=n) actbucks++;
        nr+=buck;
        recalc(i);
    }
    rec_all();
}
void init(int N, int Lo, int X[])
{
  n = N;L=Lo;
  for(i=2;i<=n;i++)
    lg[i]=lg[i/2]+1;
  for(i=1;i<=n;i++)
    v[i].first=X[i-1],v[i].second=i;
  rebucket();
}
int cate=0;
int update(int i, int y)
{
    cate++;i++;
   if(cate%buck==0)
   {
       int  nr=0;
       for(int ii=1;ii<=actbucks;ii++)
        for(int jj=1;jj<=sz[ii];jj++)
          v[++nr]=b[ii][jj];
       rebucket();
   }
   sterge(unde[i].first,unde[i].second);
   ins(i,y);
   return rec_all();
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3832 KB Output is correct
2 Correct 4 ms 3836 KB Output is correct
3 Correct 4 ms 3924 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3832 KB Output is correct
2 Correct 4 ms 3836 KB Output is correct
3 Correct 4 ms 3924 KB Output is correct
4 Correct 4 ms 3924 KB Output is correct
5 Correct 4 ms 3932 KB Output is correct
6 Correct 4 ms 3932 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3832 KB Output is correct
2 Correct 4 ms 3836 KB Output is correct
3 Correct 4 ms 3924 KB Output is correct
4 Correct 4 ms 3924 KB Output is correct
5 Correct 4 ms 3932 KB Output is correct
6 Correct 4 ms 3932 KB Output is correct
7 Correct 519 ms 5268 KB Output is correct
8 Correct 543 ms 5540 KB Output is correct
9 Correct 807 ms 6992 KB Output is correct
10 Correct 731 ms 10064 KB Output is correct
11 Correct 822 ms 10220 KB Output is correct
12 Correct 1619 ms 10220 KB Output is correct
13 Correct 660 ms 10236 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3832 KB Output is correct
2 Correct 4 ms 3836 KB Output is correct
3 Correct 4 ms 3924 KB Output is correct
4 Correct 4 ms 3924 KB Output is correct
5 Correct 4 ms 3932 KB Output is correct
6 Correct 4 ms 3932 KB Output is correct
7 Correct 519 ms 5268 KB Output is correct
8 Correct 543 ms 5540 KB Output is correct
9 Correct 807 ms 6992 KB Output is correct
10 Correct 731 ms 10064 KB Output is correct
11 Correct 822 ms 10220 KB Output is correct
12 Correct 1619 ms 10220 KB Output is correct
13 Correct 660 ms 10236 KB Output is correct
14 Correct 702 ms 10236 KB Output is correct
15 Correct 802 ms 10236 KB Output is correct
16 Correct 2457 ms 10236 KB Output is correct
17 Correct 2661 ms 10236 KB Output is correct
18 Correct 2751 ms 10236 KB Output is correct
19 Correct 1391 ms 10236 KB Output is correct
20 Correct 2670 ms 10236 KB Output is correct
21 Correct 2580 ms 10236 KB Output is correct
22 Correct 1135 ms 11516 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3832 KB Output is correct
2 Correct 4 ms 3836 KB Output is correct
3 Correct 4 ms 3924 KB Output is correct
4 Correct 4 ms 3924 KB Output is correct
5 Correct 4 ms 3932 KB Output is correct
6 Correct 4 ms 3932 KB Output is correct
7 Correct 519 ms 5268 KB Output is correct
8 Correct 543 ms 5540 KB Output is correct
9 Correct 807 ms 6992 KB Output is correct
10 Correct 731 ms 10064 KB Output is correct
11 Correct 822 ms 10220 KB Output is correct
12 Correct 1619 ms 10220 KB Output is correct
13 Correct 660 ms 10236 KB Output is correct
14 Correct 702 ms 10236 KB Output is correct
15 Correct 802 ms 10236 KB Output is correct
16 Correct 2457 ms 10236 KB Output is correct
17 Correct 2661 ms 10236 KB Output is correct
18 Correct 2751 ms 10236 KB Output is correct
19 Correct 1391 ms 10236 KB Output is correct
20 Correct 2670 ms 10236 KB Output is correct
21 Correct 2580 ms 10236 KB Output is correct
22 Correct 1135 ms 11516 KB Output is correct
23 Correct 6825 ms 12968 KB Output is correct
24 Correct 6800 ms 18064 KB Output is correct
25 Correct 6131 ms 23128 KB Output is correct
26 Correct 6068 ms 30244 KB Output is correct
27 Correct 6498 ms 33104 KB Output is correct
28 Correct 2934 ms 33104 KB Output is correct
29 Correct 2895 ms 33104 KB Output is correct
30 Correct 2944 ms 34952 KB Output is correct
31 Correct 2927 ms 37912 KB Output is correct
32 Correct 5819 ms 52488 KB Output is correct
33 Correct 5583 ms 56444 KB Output is correct
34 Correct 5307 ms 61120 KB Output is correct
35 Correct 3926 ms 65312 KB Output is correct
36 Correct 3324 ms 67184 KB Output is correct
37 Correct 8698 ms 73664 KB Output is correct
38 Correct 5005 ms 78960 KB Output is correct
39 Correct 5733 ms 80544 KB Output is correct
40 Correct 4805 ms 87444 KB Output is correct
41 Execution timed out 9070 ms 88932 KB Time limit exceeded
42 Halted 0 ms 0 KB -