oj.uz

Submission #887695

# Submission time Handle Problem Language Result Execution time Memory
887695 2023-12-15T03:04:40 Z 12345678 Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 20212 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=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;
        }
    }
}

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;
    }
    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];
    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

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8536 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8536 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 3062 ms 9816 KB Output is correct
8 Correct 3154 ms 10220 KB Output is correct
9 Correct 1693 ms 12520 KB Output is correct
10 Correct 1251 ms 12116 KB Output is correct
11 Correct 1101 ms 12224 KB Output is correct
12 Correct 3314 ms 13180 KB Output is correct
13 Correct 1144 ms 12220 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8536 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 3062 ms 9816 KB Output is correct
8 Correct 3154 ms 10220 KB Output is correct
9 Correct 1693 ms 12520 KB Output is correct
10 Correct 1251 ms 12116 KB Output is correct
11 Correct 1101 ms 12224 KB Output is correct
12 Correct 3314 ms 13180 KB Output is correct
13 Correct 1144 ms 12220 KB Output is correct
14 Correct 2012 ms 10424 KB Output is correct
15 Correct 2279 ms 10692 KB Output is correct
16 Correct 5007 ms 12968 KB Output is correct
17 Correct 5500 ms 14656 KB Output is correct
18 Correct 5650 ms 14668 KB Output is correct
19 Correct 4959 ms 13604 KB Output is correct
20 Correct 5621 ms 14676 KB Output is correct
21 Correct 5402 ms 14880 KB Output is correct
22 Correct 1991 ms 13748 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8536 KB Output is correct
2 Correct 1 ms 8536 KB Output is correct
3 Correct 1 ms 8540 KB Output is correct
4 Correct 1 ms 8536 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 3062 ms 9816 KB Output is correct
8 Correct 3154 ms 10220 KB Output is correct
9 Correct 1693 ms 12520 KB Output is correct
10 Correct 1251 ms 12116 KB Output is correct
11 Correct 1101 ms 12224 KB Output is correct
12 Correct 3314 ms 13180 KB Output is correct
13 Correct 1144 ms 12220 KB Output is correct
14 Correct 2012 ms 10424 KB Output is correct
15 Correct 2279 ms 10692 KB Output is correct
16 Correct 5007 ms 12968 KB Output is correct
17 Correct 5500 ms 14656 KB Output is correct
18 Correct 5650 ms 14668 KB Output is correct
19 Correct 4959 ms 13604 KB Output is correct
20 Correct 5621 ms 14676 KB Output is correct
21 Correct 5402 ms 14880 KB Output is correct
22 Correct 1991 ms 13748 KB Output is correct
23 Execution timed out 9055 ms 20212 KB Time limit exceeded
24 Halted 0 ms 0 KB -