oj.uz

Submission #887708

# Submission time Handle Problem Language Result Execution time Memory
887708 2023-12-15T03:32:41 Z 12345678 Dancing Elephants (IOI11_elephants) C++17
97 / 100
 9000 ms 20116 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 ((++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 1 ms 8540 KB Output is correct
2 Correct 2 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 2 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 8540 KB Output is correct
2 Correct 2 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 2706 ms 9956 KB Output is correct
8 Correct 1714 ms 10428 KB Output is correct
9 Correct 1760 ms 12476 KB Output is correct
10 Correct 1317 ms 12200 KB Output is correct
11 Correct 1195 ms 12192 KB Output is correct
12 Correct 3238 ms 13104 KB Output is correct
13 Correct 1209 ms 12196 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 2 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 2706 ms 9956 KB Output is correct
8 Correct 1714 ms 10428 KB Output is correct
9 Correct 1760 ms 12476 KB Output is correct
10 Correct 1317 ms 12200 KB Output is correct
11 Correct 1195 ms 12192 KB Output is correct
12 Correct 3238 ms 13104 KB Output is correct
13 Correct 1209 ms 12196 KB Output is correct
14 Correct 1869 ms 10180 KB Output is correct
15 Correct 2254 ms 10844 KB Output is correct
16 Correct 4903 ms 12992 KB Output is correct
17 Correct 5534 ms 14736 KB Output is correct
18 Correct 5542 ms 14872 KB Output is correct
19 Correct 5125 ms 13560 KB Output is correct
20 Correct 5536 ms 14884 KB Output is correct
21 Correct 5356 ms 14628 KB Output is correct
22 Correct 2281 ms 13564 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 2 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 2706 ms 9956 KB Output is correct
8 Correct 1714 ms 10428 KB Output is correct
9 Correct 1760 ms 12476 KB Output is correct
10 Correct 1317 ms 12200 KB Output is correct
11 Correct 1195 ms 12192 KB Output is correct
12 Correct 3238 ms 13104 KB Output is correct
13 Correct 1209 ms 12196 KB Output is correct
14 Correct 1869 ms 10180 KB Output is correct
15 Correct 2254 ms 10844 KB Output is correct
16 Correct 4903 ms 12992 KB Output is correct
17 Correct 5534 ms 14736 KB Output is correct
18 Correct 5542 ms 14872 KB Output is correct
19 Correct 5125 ms 13560 KB Output is correct
20 Correct 5536 ms 14884 KB Output is correct
21 Correct 5356 ms 14628 KB Output is correct
22 Correct 2281 ms 13564 KB Output is correct
23 Execution timed out 9028 ms 20116 KB Time limit exceeded
24 Halted 0 ms 0 KB -