oj.uz

답안 #90421

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
90421 2018-12-21T15:36:20 Z Bodo171 코끼리 (Dancing Elephants) (IOI11_elephants) C++14
97 / 100
 9000 ms 40796 KB 
#include "elephants.h"
#include <iostream>
const int nmax=150005;
const int buck=400;
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;
    for(int i=sz[wh];i>=1;i--)
    {
        poz=cb(wh,b[wh][i].first+L);
        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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 760 KB Output is correct

Subtask #2
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 2 ms 760 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 1002 ms 2072 KB Output is correct
8 Correct 1064 ms 3484 KB Output is correct
9 Correct 1457 ms 6824 KB Output is correct
10 Correct 867 ms 11440 KB Output is correct
11 Correct 682 ms 12712 KB Output is correct
12 Correct 1797 ms 12712 KB Output is correct
13 Correct 811 ms 15284 KB Output is correct

Subtask #4
47.0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 1002 ms 2072 KB Output is correct
8 Correct 1064 ms 3484 KB Output is correct
9 Correct 1457 ms 6824 KB Output is correct
10 Correct 867 ms 11440 KB Output is correct
11 Correct 682 ms 12712 KB Output is correct
12 Correct 1797 ms 12712 KB Output is correct
13 Correct 811 ms 15284 KB Output is correct
14 Correct 1340 ms 15284 KB Output is correct
15 Correct 1566 ms 15284 KB Output is correct
16 Correct 2388 ms 17144 KB Output is correct
17 Correct 2798 ms 20564 KB Output is correct
18 Correct 2757 ms 22560 KB Output is correct
19 Correct 2463 ms 24424 KB Output is correct
20 Correct 2866 ms 26592 KB Output is correct
21 Correct 2819 ms 28780 KB Output is correct
22 Correct 1488 ms 33184 KB Output is correct

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 760 KB Output is correct
2 Correct 2 ms 760 KB Output is correct
3 Correct 2 ms 760 KB Output is correct
4 Correct 2 ms 760 KB Output is correct
5 Correct 2 ms 760 KB Output is correct
6 Correct 2 ms 760 KB Output is correct
7 Correct 1002 ms 2072 KB Output is correct
8 Correct 1064 ms 3484 KB Output is correct
9 Correct 1457 ms 6824 KB Output is correct
10 Correct 867 ms 11440 KB Output is correct
11 Correct 682 ms 12712 KB Output is correct
12 Correct 1797 ms 12712 KB Output is correct
13 Correct 811 ms 15284 KB Output is correct
14 Correct 1340 ms 15284 KB Output is correct
15 Correct 1566 ms 15284 KB Output is correct
16 Correct 2388 ms 17144 KB Output is correct
17 Correct 2798 ms 20564 KB Output is correct
18 Correct 2757 ms 22560 KB Output is correct
19 Correct 2463 ms 24424 KB Output is correct
20 Correct 2866 ms 26592 KB Output is correct
21 Correct 2819 ms 28780 KB Output is correct
22 Correct 1488 ms 33184 KB Output is correct
23 Execution timed out 9072 ms 40796 KB Time limit exceeded
24 Halted 0 ms 0 KB -