oj.uz

답안 #887688

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
887688 2023-12-15T02:59:19 Z 12345678 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
97 / 100
 9000 ms 24892 KB 
#include "elephants.h"
#include <bits/stdc++.h>

using namespace std;

const int nx=150005, tx=400;
int n, c[nx], v[nx], l, cnt;
multiset<int> ms[tx];
vector<int> vl[tx];
vector<pair<int, int>> dp[tx];

void calc(int x)
{
    vl[x].resize(0);
    for (auto a:ms[x]) vl[x].push_back(a);
    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;
        }
        //printf("val %d %d %d %d\n", i, vl[x][i], dp[x][i].first, dp[x][i].second);
    }
    //cout<<"this "<<x<<'\n';
    //for (int i=0; i<vl[x].size(); i++) cout<<i<<' '<<vl[x][i]<<' '<<dp[x][i].first<<' '<<dp[x][i].second<<'\n';
}

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++) ms[i].clear();
    for (int i=0; i<n; i++) c[d[i].second]=i/tx, ms[i/tx].insert(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;
        //printf("query %d %d %d\n", i, lst, idx);
    }
    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)
{
    //cout<<"new"<<'\n';
    if (i%tx==0) 
    {
        v[i]=y;
        build();
        return query();
    }
    int loc=c[i];
    ms[loc].erase(ms[loc].find(v[i]));
    v[i]=y;
    calc(loc);
    for (int j=0; j<tx; j++)
    {
        if (j==tx-1)
        {
            ms[j].insert(y);
            c[i]=j;
            calc(j);
        }
        else if (!vl[j].empty()&&vl[j][vl[j].size()-1]>=y)
        {
            ms[j].insert(y);
            c[i]=j;
            calc(j);
            break;
        }
    }
    return query();
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 1 ms 8536 KB Output is correct
7 Correct 3152 ms 9916 KB Output is correct
8 Correct 3228 ms 11448 KB Output is correct
9 Correct 1871 ms 13976 KB Output is correct
10 Correct 1400 ms 13756 KB Output is correct
11 Correct 1240 ms 13500 KB Output is correct
12 Correct 3782 ms 14428 KB Output is correct
13 Correct 1257 ms 13324 KB Output is correct

Subtask #4
47.0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 1 ms 8536 KB Output is correct
7 Correct 3152 ms 9916 KB Output is correct
8 Correct 3228 ms 11448 KB Output is correct
9 Correct 1871 ms 13976 KB Output is correct
10 Correct 1400 ms 13756 KB Output is correct
11 Correct 1240 ms 13500 KB Output is correct
12 Correct 3782 ms 14428 KB Output is correct
13 Correct 1257 ms 13324 KB Output is correct
14 Correct 2276 ms 11704 KB Output is correct
15 Correct 2644 ms 12828 KB Output is correct
16 Correct 5441 ms 14772 KB Output is correct
17 Correct 6089 ms 16676 KB Output is correct
18 Correct 6289 ms 16844 KB Output is correct
19 Correct 5098 ms 15708 KB Output is correct
20 Correct 6975 ms 16700 KB Output is correct
21 Correct 6425 ms 16664 KB Output is correct
22 Correct 2237 ms 15144 KB Output is correct

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8540 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 2 ms 8540 KB Output is correct
5 Correct 2 ms 8540 KB Output is correct
6 Correct 1 ms 8536 KB Output is correct
7 Correct 3152 ms 9916 KB Output is correct
8 Correct 3228 ms 11448 KB Output is correct
9 Correct 1871 ms 13976 KB Output is correct
10 Correct 1400 ms 13756 KB Output is correct
11 Correct 1240 ms 13500 KB Output is correct
12 Correct 3782 ms 14428 KB Output is correct
13 Correct 1257 ms 13324 KB Output is correct
14 Correct 2276 ms 11704 KB Output is correct
15 Correct 2644 ms 12828 KB Output is correct
16 Correct 5441 ms 14772 KB Output is correct
17 Correct 6089 ms 16676 KB Output is correct
18 Correct 6289 ms 16844 KB Output is correct
19 Correct 5098 ms 15708 KB Output is correct
20 Correct 6975 ms 16700 KB Output is correct
21 Correct 6425 ms 16664 KB Output is correct
22 Correct 2237 ms 15144 KB Output is correct
23 Execution timed out 9052 ms 24892 KB Time limit exceeded
24 Halted 0 ms 0 KB -