oj.uz

Submission #1030904

# Submission time Handle Problem Language Result Execution time Memory
1030904 2024-07-22T11:45:08 Z idas Dancing Elephants (IOI11_elephants) C++11
100 / 100
 6836 ms 28088 KB 
#include "elephants.h"

#include <bits/stdc++.h>
#define FOR(i, begin, end) for(int i=(begin); i<(end); i++)
#define pb push_back
#define s second
#define f first

using namespace std;
typedef pair<int, int> pii;

const int MxN=150001, C=388, INF=1e9;

int n, l, x[MxN], dp[MxN], far[MxN], gr[MxN], max_block;
vector<pii> block[C];

void build_block(int in)
{
    int j=block[in].size();
    for(int k=block[in].size()-1; k>=0; k--){
        int i=block[in][k].s;
        while(j-1>k && block[in][j-1].f>x[i]+l) j--;
        if(j==block[in].size()) dp[i]=1, far[i]=x[i]+l;
        else{
            int nxt=block[in][j].s;
            dp[i]=dp[nxt]+1;
            far[i]=far[nxt];
        }
    }
}

void build()
{
    vector<pii> vec;
    FOR(i, 0, n) vec.pb({x[i],i});

    sort(vec.begin(), vec.end()); // might be possible to optimize this

    FOR(i, 0, max_block+1) block[i].clear();

    max_block=0;
    FOR(i, 0, n)
    {
        int in=i/C;
        block[in].pb(vec[i]);
        gr[vec[i].s]=in;
        max_block=max(max_block, in);
    }

    FOR(i, 0, max_block+1) build_block(i);
}

void change_pos(int i, int y)
{
    int in=gr[i];
    block[in].erase(lower_bound(block[in].begin(), block[in].end(), make_pair(x[i],i)));
    build_block(in);

    x[i]=y;

    int nxt_in=0;
    FOR(id, 0, max_block+1) // might be possible to optimize this
    {
        if(block[id].empty()) continue;
        if(block[id][0].f<=x[i]) nxt_in=id;
    }

    gr[i]=nxt_in;
    block[nxt_in].insert(upper_bound(block[nxt_in].begin(), block[nxt_in].end(), make_pair(x[i],i)), {x[i],i});
    build_block(nxt_in);
}

int answer()
{
    int farr=-1, ret=0;
    FOR(i, 0, max_block+1)
    {
        if(block[i].empty() || block[i].back().f<=farr) continue;

        int l0=0, r0=block[i].size();
        while(l0<r0){
            int m=(l0+r0)/2;
            if(block[i][m].f>farr) r0=m;
            else l0=m+1;
        }

//        cout << i << ": " << l0 << '\n';

        assert(l0<block[i].size());

        assert(block[i][l0].f>farr);

        ret+=dp[block[i][l0].s];
        farr=far[block[i][l0].s];
    }
    return ret;
}

void print_block(int in)
{
    for(auto it : block[in]){
        cout << it.f << " " << it.s << '\n';
    }
}

void print_blocks()
{
    FOR(i, 0, max_block+1)
    {
        cout << "block " << i << ":\n";
        print_block(i);
    }
}

void init(int N, int L, int X[])
{
    n=N; l=L; FOR(i, 0, n) x[i]=X[i];
}

int counter=0;
int update(int i, int y)
{
    if(counter%C==0) build();
    change_pos(i, y);
    counter++;

//    cout << "update (" << i << ", " << y << "):\n";
//
//    print_blocks();

    return answer();
}

Compilation message

elephants.cpp: In function 'void build_block(int)':
elephants.cpp:23:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   23 |         if(j==block[in].size()) dp[i]=1, far[i]=x[i]+l;
      |            ~^~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from elephants.cpp:3:
elephants.cpp: In function 'int answer()':
elephants.cpp:89:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   89 |         assert(l0<block[i].size());
      |                ~~^~~~~~~~~~~~~~~~

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 1 ms 10744 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 1 ms 10744 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 1 ms 10688 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 1 ms 10744 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 1 ms 10688 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct
7 Correct 226 ms 14292 KB Output is correct
8 Correct 238 ms 12588 KB Output is correct
9 Correct 463 ms 15896 KB Output is correct
10 Correct 541 ms 15712 KB Output is correct
11 Correct 495 ms 15760 KB Output is correct
12 Correct 826 ms 15900 KB Output is correct
13 Correct 500 ms 15464 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 1 ms 10744 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 1 ms 10688 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct
7 Correct 226 ms 14292 KB Output is correct
8 Correct 238 ms 12588 KB Output is correct
9 Correct 463 ms 15896 KB Output is correct
10 Correct 541 ms 15712 KB Output is correct
11 Correct 495 ms 15760 KB Output is correct
12 Correct 826 ms 15900 KB Output is correct
13 Correct 500 ms 15464 KB Output is correct
14 Correct 394 ms 17032 KB Output is correct
15 Correct 410 ms 16996 KB Output is correct
16 Correct 1295 ms 18192 KB Output is correct
17 Correct 1662 ms 19484 KB Output is correct
18 Correct 1687 ms 19484 KB Output is correct
19 Correct 1014 ms 19472 KB Output is correct
20 Correct 1526 ms 19332 KB Output is correct
21 Correct 1487 ms 19268 KB Output is correct
22 Correct 897 ms 18880 KB Output is correct

Subtask #5
3.0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 10584 KB Output is correct
2 Correct 1 ms 10744 KB Output is correct
3 Correct 1 ms 10588 KB Output is correct
4 Correct 1 ms 10588 KB Output is correct
5 Correct 1 ms 10688 KB Output is correct
6 Correct 1 ms 10588 KB Output is correct
7 Correct 226 ms 14292 KB Output is correct
8 Correct 238 ms 12588 KB Output is correct
9 Correct 463 ms 15896 KB Output is correct
10 Correct 541 ms 15712 KB Output is correct
11 Correct 495 ms 15760 KB Output is correct
12 Correct 826 ms 15900 KB Output is correct
13 Correct 500 ms 15464 KB Output is correct
14 Correct 394 ms 17032 KB Output is correct
15 Correct 410 ms 16996 KB Output is correct
16 Correct 1295 ms 18192 KB Output is correct
17 Correct 1662 ms 19484 KB Output is correct
18 Correct 1687 ms 19484 KB Output is correct
19 Correct 1014 ms 19472 KB Output is correct
20 Correct 1526 ms 19332 KB Output is correct
21 Correct 1487 ms 19268 KB Output is correct
22 Correct 897 ms 18880 KB Output is correct
23 Correct 3449 ms 27076 KB Output is correct
24 Correct 3603 ms 26924 KB Output is correct
25 Correct 2821 ms 26872 KB Output is correct
26 Correct 4164 ms 26940 KB Output is correct
27 Correct 4611 ms 26784 KB Output is correct
28 Correct 747 ms 17752 KB Output is correct
29 Correct 683 ms 17744 KB Output is correct
30 Correct 709 ms 17744 KB Output is correct
31 Correct 703 ms 18000 KB Output is correct
32 Correct 3664 ms 26452 KB Output is correct
33 Correct 3712 ms 25616 KB Output is correct
34 Correct 4000 ms 26504 KB Output is correct
35 Correct 3698 ms 26912 KB Output is correct
36 Correct 2938 ms 26288 KB Output is correct
37 Correct 5953 ms 28088 KB Output is correct
38 Correct 3749 ms 25756 KB Output is correct
39 Correct 3887 ms 26716 KB Output is correct
40 Correct 3868 ms 25956 KB Output is correct
41 Correct 6509 ms 26480 KB Output is correct
42 Correct 6836 ms 26508 KB Output is correct