oj.uz

Submission #887944

# Submission time Handle Problem Language Result Execution time Memory
887944 2023-12-15T14:46:58 Z 12345678 Dancing Elephants (IOI11_elephants) C++17
100 / 100
 5965 ms 21900 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;
    deque<int> dq;
    dq.push_back(INT_MAX);
    for (int i=vl[x].size()-1; i>=0; i--)
    {
        while (dq.size()>=2)
        {
            auto tmp=dq.back();
            dq.pop_back();
            if (vl[x][dq.back()]<=vl[x][i]+l) 
            {
                dq.push_back(tmp);
                break; 
            }
        }
        if (dq.back()==INT_MAX) 
        {
            dp[x][i].first=vl[x][i]+l;
            dp[x][i].second=1;
        }
        else
        {
            dp[x][i].first=dp[x][dq.back()].first;
            dp[x][i].second=dp[x][dq.back()].second+1;
        }
        dq.push_front(i);
        //if (cnt==5) cout<<x<<' '<<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;
        //if (cnt==5) cout<<i<<' '<<res<<' '<<lst<<'\n';
    }
    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 ((++cnt)%2000==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 1 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 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 1 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 867 ms 10372 KB Output is correct
8 Correct 894 ms 10760 KB Output is correct
9 Correct 671 ms 12340 KB Output is correct
10 Correct 883 ms 12364 KB Output is correct
11 Correct 896 ms 12228 KB Output is correct
12 Correct 1155 ms 13000 KB Output is correct
13 Correct 937 ms 12228 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 1 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 867 ms 10372 KB Output is correct
8 Correct 894 ms 10760 KB Output is correct
9 Correct 671 ms 12340 KB Output is correct
10 Correct 883 ms 12364 KB Output is correct
11 Correct 896 ms 12228 KB Output is correct
12 Correct 1155 ms 13000 KB Output is correct
13 Correct 937 ms 12228 KB Output is correct
14 Correct 1243 ms 10612 KB Output is correct
15 Correct 852 ms 10708 KB Output is correct
16 Correct 1878 ms 12972 KB Output is correct
17 Correct 1940 ms 14700 KB Output is correct
18 Correct 1979 ms 14680 KB Output is correct
19 Correct 1778 ms 13596 KB Output is correct
20 Correct 1890 ms 14692 KB Output is correct
21 Correct 1830 ms 14884 KB Output is correct
22 Correct 1355 ms 13588 KB Output is correct

Subtask #5
3.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 1 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 867 ms 10372 KB Output is correct
8 Correct 894 ms 10760 KB Output is correct
9 Correct 671 ms 12340 KB Output is correct
10 Correct 883 ms 12364 KB Output is correct
11 Correct 896 ms 12228 KB Output is correct
12 Correct 1155 ms 13000 KB Output is correct
13 Correct 937 ms 12228 KB Output is correct
14 Correct 1243 ms 10612 KB Output is correct
15 Correct 852 ms 10708 KB Output is correct
16 Correct 1878 ms 12972 KB Output is correct
17 Correct 1940 ms 14700 KB Output is correct
18 Correct 1979 ms 14680 KB Output is correct
19 Correct 1778 ms 13596 KB Output is correct
20 Correct 1890 ms 14692 KB Output is correct
21 Correct 1830 ms 14884 KB Output is correct
22 Correct 1355 ms 13588 KB Output is correct
23 Correct 3779 ms 20808 KB Output is correct
24 Correct 3913 ms 20988 KB Output is correct
25 Correct 3242 ms 20052 KB Output is correct
26 Correct 4500 ms 19004 KB Output is correct
27 Correct 5965 ms 19024 KB Output is correct
28 Correct 2523 ms 9452 KB Output is correct
29 Correct 2481 ms 9092 KB Output is correct
30 Correct 2575 ms 9072 KB Output is correct
31 Correct 2475 ms 9300 KB Output is correct
32 Correct 3727 ms 19008 KB Output is correct
33 Correct 3334 ms 19012 KB Output is correct
34 Correct 3944 ms 19008 KB Output is correct
35 Correct 4312 ms 21900 KB Output is correct
36 Correct 4813 ms 19024 KB Output is correct
37 Correct 5761 ms 21228 KB Output is correct
38 Correct 4024 ms 19012 KB Output is correct
39 Correct 5447 ms 19020 KB Output is correct
40 Correct 3963 ms 19008 KB Output is correct
41 Correct 5820 ms 21384 KB Output is correct
42 Correct 5561 ms 21680 KB Output is correct