oj.uz

답안 #90410

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
90410 2018-12-21T15:00:37 Z Bodo171 코끼리 (Dancing Elephants) (IOI11_elephants) C++14
26 / 100
 17 ms 1940 KB 
#include "elephants.h"
#include <iostream>
const int nmax=150005;
const int buck=400;
const int B=buck+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(i=1;i<=buck;i++)
        for(j=1;j<=sz[i];j++)
          v[++nr]=b[i][j];
       rebucket();
   }
   sterge(unde[i].first,unde[i].second);
   ins(i,y);
   return rec_all();
}

Compilation message

elephants.cpp: In function 'int cb(int, int)':
elephants.cpp:32:22: warning: suggest parentheses around comparison in operand of '&' [-Wparentheses]
         if(ret+(1<<p)<=sz[wh]&b[wh][ret+(1<<p)].first<=val)
            ~~~~~~~~~~^~~~~~~~

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 792 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 792 KB Output is correct
4 Correct 2 ms 792 KB Output is correct
5 Correct 2 ms 792 KB Output is correct
6 Correct 2 ms 792 KB Output is correct

Subtask #3
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 792 KB Output is correct
4 Correct 2 ms 792 KB Output is correct
5 Correct 2 ms 792 KB Output is correct
6 Correct 2 ms 792 KB Output is correct
7 Incorrect 17 ms 1940 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #4
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 792 KB Output is correct
4 Correct 2 ms 792 KB Output is correct
5 Correct 2 ms 792 KB Output is correct
6 Correct 2 ms 792 KB Output is correct
7 Incorrect 17 ms 1940 KB Output isn't correct
8 Halted 0 ms 0 KB -

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 792 KB Output is correct
4 Correct 2 ms 792 KB Output is correct
5 Correct 2 ms 792 KB Output is correct
6 Correct 2 ms 792 KB Output is correct
7 Incorrect 17 ms 1940 KB Output isn't correct
8 Halted 0 ms 0 KB -