oj.uz

Submission #887697

# Submission time Handle Problem Language Result Execution time Memory
887697 2023-12-15T03:06:41 Z 12345678 Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 20440 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;
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 8540 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 8540 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 8792 KB Output is correct
5 Correct 2 ms 8676 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 8540 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 8792 KB Output is correct
5 Correct 2 ms 8676 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 2963 ms 9916 KB Output is correct
8 Correct 3051 ms 10376 KB Output is correct
9 Correct 1608 ms 12500 KB Output is correct
10 Correct 1310 ms 12200 KB Output is correct
11 Correct 1187 ms 12224 KB Output is correct
12 Correct 3421 ms 13396 KB Output is correct
13 Correct 1205 ms 12128 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 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 8792 KB Output is correct
5 Correct 2 ms 8676 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 2963 ms 9916 KB Output is correct
8 Correct 3051 ms 10376 KB Output is correct
9 Correct 1608 ms 12500 KB Output is correct
10 Correct 1310 ms 12200 KB Output is correct
11 Correct 1187 ms 12224 KB Output is correct
12 Correct 3421 ms 13396 KB Output is correct
13 Correct 1205 ms 12128 KB Output is correct
14 Correct 1876 ms 10320 KB Output is correct
15 Correct 2254 ms 10788 KB Output is correct
16 Correct 5009 ms 12972 KB Output is correct
17 Correct 5883 ms 14640 KB Output is correct
18 Correct 5595 ms 15152 KB Output is correct
19 Correct 5110 ms 13552 KB Output is correct
20 Correct 5571 ms 14680 KB Output is correct
21 Correct 5458 ms 14864 KB Output is correct
22 Correct 2219 ms 13604 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 8540 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 8792 KB Output is correct
5 Correct 2 ms 8676 KB Output is correct
6 Correct 1 ms 8540 KB Output is correct
7 Correct 2963 ms 9916 KB Output is correct
8 Correct 3051 ms 10376 KB Output is correct
9 Correct 1608 ms 12500 KB Output is correct
10 Correct 1310 ms 12200 KB Output is correct
11 Correct 1187 ms 12224 KB Output is correct
12 Correct 3421 ms 13396 KB Output is correct
13 Correct 1205 ms 12128 KB Output is correct
14 Correct 1876 ms 10320 KB Output is correct
15 Correct 2254 ms 10788 KB Output is correct
16 Correct 5009 ms 12972 KB Output is correct
17 Correct 5883 ms 14640 KB Output is correct
18 Correct 5595 ms 15152 KB Output is correct
19 Correct 5110 ms 13552 KB Output is correct
20 Correct 5571 ms 14680 KB Output is correct
21 Correct 5458 ms 14864 KB Output is correct
22 Correct 2219 ms 13604 KB Output is correct
23 Execution timed out 9077 ms 20440 KB Time limit exceeded
24 Halted 0 ms 0 KB -