oj.uz

Submission #90422

# Submission time Handle Problem Language Result Execution time Memory
90422 2018-12-21T15:41:35 Z Bodo171 Dancing Elephants (IOI11_elephants) C++14
50 / 100
 2274 ms 10284 KB 
#include "elephants.h"
#include <iostream>
const int nmax=150005;
const int buck=800;
const int B=2*400+5;
using namespace std;
pair<int,int> dp[2*B][2*B],b[2*B][2*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 3832 KB Output is correct
3 Correct 4 ms 3896 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 3832 KB Output is correct
3 Correct 4 ms 3896 KB Output is correct
4 Correct 4 ms 3896 KB Output is correct
5 Correct 4 ms 3896 KB Output is correct
6 Correct 4 ms 3896 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 3832 KB Output is correct
3 Correct 4 ms 3896 KB Output is correct
4 Correct 4 ms 3896 KB Output is correct
5 Correct 4 ms 3896 KB Output is correct
6 Correct 4 ms 3896 KB Output is correct
7 Correct 484 ms 5156 KB Output is correct
8 Correct 485 ms 5584 KB Output is correct
9 Correct 649 ms 7084 KB Output is correct
10 Correct 517 ms 10284 KB Output is correct
11 Correct 546 ms 10284 KB Output is correct
12 Correct 1366 ms 10284 KB Output is correct
13 Correct 531 ms 10284 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3832 KB Output is correct
2 Correct 4 ms 3832 KB Output is correct
3 Correct 4 ms 3896 KB Output is correct
4 Correct 4 ms 3896 KB Output is correct
5 Correct 4 ms 3896 KB Output is correct
6 Correct 4 ms 3896 KB Output is correct
7 Correct 484 ms 5156 KB Output is correct
8 Correct 485 ms 5584 KB Output is correct
9 Correct 649 ms 7084 KB Output is correct
10 Correct 517 ms 10284 KB Output is correct
11 Correct 546 ms 10284 KB Output is correct
12 Correct 1366 ms 10284 KB Output is correct
13 Correct 531 ms 10284 KB Output is correct
14 Correct 671 ms 10284 KB Output is correct
15 Correct 719 ms 10284 KB Output is correct
16 Correct 2123 ms 10284 KB Output is correct
17 Correct 2163 ms 10284 KB Output is correct
18 Correct 2274 ms 10284 KB Output is correct
19 Incorrect 41 ms 10284 KB Output isn't correct
20 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 3832 KB Output is correct
2 Correct 4 ms 3832 KB Output is correct
3 Correct 4 ms 3896 KB Output is correct
4 Correct 4 ms 3896 KB Output is correct
5 Correct 4 ms 3896 KB Output is correct
6 Correct 4 ms 3896 KB Output is correct
7 Correct 484 ms 5156 KB Output is correct
8 Correct 485 ms 5584 KB Output is correct
9 Correct 649 ms 7084 KB Output is correct
10 Correct 517 ms 10284 KB Output is correct
11 Correct 546 ms 10284 KB Output is correct
12 Correct 1366 ms 10284 KB Output is correct
13 Correct 531 ms 10284 KB Output is correct
14 Correct 671 ms 10284 KB Output is correct
15 Correct 719 ms 10284 KB Output is correct
16 Correct 2123 ms 10284 KB Output is correct
17 Correct 2163 ms 10284 KB Output is correct
18 Correct 2274 ms 10284 KB Output is correct
19 Incorrect 41 ms 10284 KB Output isn't correct
20 Halted 0 ms 0 KB -