oj.uz

Submission #90425

# Submission time Handle Problem Language Result Execution time Memory
90425 2018-12-21T15:49:37 Z Bodo171 Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 15264 KB 
#include "elephants.h"
#include <iostream>
const int nmax=150005;
const int buck=400;
const int B=4*buck+5;
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 3 ms 2168 KB Output is correct
2 Correct 3 ms 2176 KB Output is correct
3 Correct 3 ms 2208 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2168 KB Output is correct
2 Correct 3 ms 2176 KB Output is correct
3 Correct 3 ms 2208 KB Output is correct
4 Correct 3 ms 2208 KB Output is correct
5 Correct 3 ms 2248 KB Output is correct
6 Correct 3 ms 2248 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2168 KB Output is correct
2 Correct 3 ms 2176 KB Output is correct
3 Correct 3 ms 2208 KB Output is correct
4 Correct 3 ms 2208 KB Output is correct
5 Correct 3 ms 2248 KB Output is correct
6 Correct 3 ms 2248 KB Output is correct
7 Correct 318 ms 3912 KB Output is correct
8 Correct 374 ms 4148 KB Output is correct
9 Correct 655 ms 6080 KB Output is correct
10 Correct 585 ms 7520 KB Output is correct
11 Correct 510 ms 7520 KB Output is correct
12 Correct 1106 ms 7520 KB Output is correct
13 Correct 599 ms 7548 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2168 KB Output is correct
2 Correct 3 ms 2176 KB Output is correct
3 Correct 3 ms 2208 KB Output is correct
4 Correct 3 ms 2208 KB Output is correct
5 Correct 3 ms 2248 KB Output is correct
6 Correct 3 ms 2248 KB Output is correct
7 Correct 318 ms 3912 KB Output is correct
8 Correct 374 ms 4148 KB Output is correct
9 Correct 655 ms 6080 KB Output is correct
10 Correct 585 ms 7520 KB Output is correct
11 Correct 510 ms 7520 KB Output is correct
12 Correct 1106 ms 7520 KB Output is correct
13 Correct 599 ms 7548 KB Output is correct
14 Correct 472 ms 7548 KB Output is correct
15 Correct 604 ms 7548 KB Output is correct
16 Correct 1653 ms 7548 KB Output is correct
17 Correct 1954 ms 7548 KB Output is correct
18 Correct 2017 ms 7548 KB Output is correct
19 Correct 1221 ms 7548 KB Output is correct
20 Correct 1983 ms 7548 KB Output is correct
21 Correct 1959 ms 7548 KB Output is correct
22 Correct 1110 ms 8868 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2168 KB Output is correct
2 Correct 3 ms 2176 KB Output is correct
3 Correct 3 ms 2208 KB Output is correct
4 Correct 3 ms 2208 KB Output is correct
5 Correct 3 ms 2248 KB Output is correct
6 Correct 3 ms 2248 KB Output is correct
7 Correct 318 ms 3912 KB Output is correct
8 Correct 374 ms 4148 KB Output is correct
9 Correct 655 ms 6080 KB Output is correct
10 Correct 585 ms 7520 KB Output is correct
11 Correct 510 ms 7520 KB Output is correct
12 Correct 1106 ms 7520 KB Output is correct
13 Correct 599 ms 7548 KB Output is correct
14 Correct 472 ms 7548 KB Output is correct
15 Correct 604 ms 7548 KB Output is correct
16 Correct 1653 ms 7548 KB Output is correct
17 Correct 1954 ms 7548 KB Output is correct
18 Correct 2017 ms 7548 KB Output is correct
19 Correct 1221 ms 7548 KB Output is correct
20 Correct 1983 ms 7548 KB Output is correct
21 Correct 1959 ms 7548 KB Output is correct
22 Correct 1110 ms 8868 KB Output is correct
23 Correct 7671 ms 12972 KB Output is correct
24 Correct 7625 ms 13052 KB Output is correct
25 Correct 7392 ms 13168 KB Output is correct
26 Correct 8106 ms 14024 KB Output is correct
27 Correct 7237 ms 14024 KB Output is correct
28 Correct 1386 ms 14024 KB Output is correct
29 Correct 1334 ms 14024 KB Output is correct
30 Correct 1426 ms 14024 KB Output is correct
31 Correct 1360 ms 14024 KB Output is correct
32 Correct 5544 ms 14552 KB Output is correct
33 Correct 5135 ms 14552 KB Output is correct
34 Correct 7608 ms 14580 KB Output is correct
35 Correct 4370 ms 15264 KB Output is correct
36 Correct 3190 ms 15264 KB Output is correct
37 Execution timed out 9015 ms 15264 KB Time limit exceeded
38 Halted 0 ms 0 KB -