oj.uz

Submission #887693

# Submission time Handle Problem Language Result Execution time Memory
887693 2023-12-15T03:02:01 Z 12345678 Dancing Elephants (IOI11_elephants) C++17
97 / 100
 5869 ms 33620 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=380;
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 8540 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 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 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 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 8540 KB Output is correct
7 Correct 2889 ms 9760 KB Output is correct
8 Correct 2958 ms 10204 KB Output is correct
9 Correct 1746 ms 12716 KB Output is correct
10 Correct 1273 ms 12200 KB Output is correct
11 Correct 1144 ms 12196 KB Output is correct
12 Correct 3163 ms 12980 KB Output is correct
13 Correct 1155 ms 12208 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 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 8540 KB Output is correct
7 Correct 2889 ms 9760 KB Output is correct
8 Correct 2958 ms 10204 KB Output is correct
9 Correct 1746 ms 12716 KB Output is correct
10 Correct 1273 ms 12200 KB Output is correct
11 Correct 1144 ms 12196 KB Output is correct
12 Correct 3163 ms 12980 KB Output is correct
13 Correct 1155 ms 12208 KB Output is correct
14 Correct 1807 ms 10424 KB Output is correct
15 Correct 2176 ms 10692 KB Output is correct
16 Correct 4750 ms 12976 KB Output is correct
17 Correct 5348 ms 14656 KB Output is correct
18 Correct 5639 ms 14724 KB Output is correct
19 Correct 5017 ms 13560 KB Output is correct
20 Correct 5869 ms 14668 KB Output is correct
21 Correct 5359 ms 14624 KB Output is correct
22 Correct 2137 ms 13568 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 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 8540 KB Output is correct
7 Correct 2889 ms 9760 KB Output is correct
8 Correct 2958 ms 10204 KB Output is correct
9 Correct 1746 ms 12716 KB Output is correct
10 Correct 1273 ms 12200 KB Output is correct
11 Correct 1144 ms 12196 KB Output is correct
12 Correct 3163 ms 12980 KB Output is correct
13 Correct 1155 ms 12208 KB Output is correct
14 Correct 1807 ms 10424 KB Output is correct
15 Correct 2176 ms 10692 KB Output is correct
16 Correct 4750 ms 12976 KB Output is correct
17 Correct 5348 ms 14656 KB Output is correct
18 Correct 5639 ms 14724 KB Output is correct
19 Correct 5017 ms 13560 KB Output is correct
20 Correct 5869 ms 14668 KB Output is correct
21 Correct 5359 ms 14624 KB Output is correct
22 Correct 2137 ms 13568 KB Output is correct
23 Runtime error 68 ms 33620 KB Execution killed with signal 11
24 Halted 0 ms 0 KB -