oj.uz

답안 #887704

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
887704 2023-12-15T03:24:01 Z 12345678 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
0 / 100
 1 ms 8540 KB 
#include "elephants.h"
#include <bits/stdc++.h>
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
using namespace std;
 
const int nx=150005, tx=390;
int n, c[nx], v[nx], l, cnt;
vector<int> vl[tx];
vector<pair<int, int>> dp[tx];
 
void calc(int x)
{
    sort(vl[x].begin(), vl[x].end());
    dp[x].resize(vl[x].size());
    if (vl[x].size()==0) return;
    for (int i=vl[x].size()-1; i>=0; i--)
    {
        if (upper_bound(vl[x].begin(), vl[x].end(), vl[x][i]+l)==vl[x].end())
        {
            dp[x][i].first=vl[x][i]+l;
            dp[x][i].second=1;
        }
        else
        {
            int idx=upper_bound(vl[x].begin(), vl[x].end(), vl[x][i]+l)-vl[x].begin();
            dp[x][i].first=dp[x][idx].first;
            dp[x][i].second=dp[x][idx].second+1;
        }
    }
}
 
void build()
{
    vector<pair<int, int>> d(n);
    for (int i=0; i<n; i++) d[i].first=v[i], d[i].second=i;
    sort(d.begin(), d.end());
    for (int i=0; i<tx; i++) vl[i].clear();
    for (int i=0; i<n; i++) c[d[i].second]=i/tx, vl[i/tx].push_back(d[i].first);
    for (int i=0; i<tx; i++) calc(i);
}
 
int query()
{
    int lst=-1, res=0;
    for (int i=0; i<tx; i++)
    {
        if (vl[i].empty()||lst>=vl[i][vl[i].size()-1]) continue;
        int idx=upper_bound(vl[i].begin(), vl[i].end(), lst)-vl[i].begin();
        res+=dp[i][idx].second;
        lst=dp[i][idx].first;
    }
    return res;
}
 
void init(int N, int L, int X[])
{
    n=N; l=L;
    for (int i=0; i<n; i++) v[i]=X[i];
    build();
}
 
int update(int i, int y)
{
    if (i%tx==0) 
    {
        v[i]=y;
        build();
        return query();
    }
    int loc=c[i];
    vector<int> tmp;
    bool f=0;
    for (int i=0; i<vl[loc].size(); i++)
    {
        if (vl[loc][i]==v[i]&&!f)
        {
            f=1; continue;
        }
        else tmp.push_back(v[i]);
    }
    vl[loc]=tmp;
    v[i]=y;
    calc(loc);
    for (int j=0; j<tx; j++)
    {
        if (j==tx-1)
        {
            vl[j].push_back(y);
            c[i]=j;
            calc(j);
        }
        else if (!vl[j].empty()&&vl[j][vl[j].size()-1]>=y)
        {
            vl[j].push_back(y);
            c[i]=j;
            calc(j);
            break;
        }
    }
    return query();
}

Compilation message

elephants.cpp: In function 'int update(int, int)':
elephants.cpp:74:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |     for (int i=0; i<vl[loc].size(); i++)
      |                   ~^~~~~~~~~~~~~~~

Subtask #1
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 8540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 8540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 8540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 8540 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 8540 KB Output isn't correct
2 Halted 0 ms 0 KB -