oj.uz

Submission #887940

# Submission time Handle Problem Language Result Execution time Memory
887940 2023-12-15T14:40:30 Z 12345678 Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 25740 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)%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 2 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 2 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 8536 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 2 ms 8676 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 8536 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 2 ms 8676 KB Output is correct
7 Correct 661 ms 10596 KB Output is correct
8 Correct 695 ms 11208 KB Output is correct
9 Correct 1214 ms 14064 KB Output is correct
10 Correct 1169 ms 13536 KB Output is correct
11 Correct 1037 ms 13472 KB Output is correct
12 Correct 1919 ms 14412 KB Output is correct
13 Correct 1130 ms 13328 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 8536 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 2 ms 8676 KB Output is correct
7 Correct 661 ms 10596 KB Output is correct
8 Correct 695 ms 11208 KB Output is correct
9 Correct 1214 ms 14064 KB Output is correct
10 Correct 1169 ms 13536 KB Output is correct
11 Correct 1037 ms 13472 KB Output is correct
12 Correct 1919 ms 14412 KB Output is correct
13 Correct 1130 ms 13328 KB Output is correct
14 Correct 1205 ms 11700 KB Output is correct
15 Correct 1199 ms 12116 KB Output is correct
16 Correct 2794 ms 14780 KB Output is correct
17 Correct 3218 ms 16924 KB Output is correct
18 Correct 3344 ms 16604 KB Output is correct
19 Correct 2178 ms 15716 KB Output is correct
20 Correct 3264 ms 16676 KB Output is correct
21 Correct 3185 ms 16784 KB Output is correct
22 Correct 1847 ms 15148 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 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 8536 KB Output is correct
5 Correct 2 ms 8536 KB Output is correct
6 Correct 2 ms 8676 KB Output is correct
7 Correct 661 ms 10596 KB Output is correct
8 Correct 695 ms 11208 KB Output is correct
9 Correct 1214 ms 14064 KB Output is correct
10 Correct 1169 ms 13536 KB Output is correct
11 Correct 1037 ms 13472 KB Output is correct
12 Correct 1919 ms 14412 KB Output is correct
13 Correct 1130 ms 13328 KB Output is correct
14 Correct 1205 ms 11700 KB Output is correct
15 Correct 1199 ms 12116 KB Output is correct
16 Correct 2794 ms 14780 KB Output is correct
17 Correct 3218 ms 16924 KB Output is correct
18 Correct 3344 ms 16604 KB Output is correct
19 Correct 2178 ms 15716 KB Output is correct
20 Correct 3264 ms 16676 KB Output is correct
21 Correct 3185 ms 16784 KB Output is correct
22 Correct 1847 ms 15148 KB Output is correct
23 Correct 8337 ms 25740 KB Output is correct
24 Correct 8859 ms 25516 KB Output is correct
25 Correct 7188 ms 24900 KB Output is correct
26 Correct 8048 ms 24004 KB Output is correct
27 Execution timed out 9002 ms 23852 KB Time limit exceeded
28 Halted 0 ms 0 KB -