oj.uz

Submission #97221

# Submission time Handle Problem Language Result Execution time Memory
97221 2019-02-14T12:44:28 Z Alexa2001 Dancing Elephants (IOI11_elephants) C++17
10 / 100
 9000 ms 512 KB 
#include "elephants.h"
#include <bits/stdc++.h>

using namespace std;

const int Nmax = 7e4 + 5, lg = 17, inf = 2e9;
const int BS = 300;

typedef pair<int,int> Pair;

int n, L, nr_upd, where[Nmax];
set<Pair> S;
set<int> bad;

int go[lg+2][Nmax];


void init(int N, int _L, int X[])
{
    nr_upd = 0;
    int i; L = _L; n = N;
    for(i=0; i<n; ++i)
    {
        where[i] = X[i];
        S.insert({X[i], i});
    }
}

void refresh_all()
{
    int i, j;
    set<Pair> :: iterator itt;

    for(auto it : S)
    {
        itt = S.upper_bound({ it.first + L, inf });
        go[0][it.second] = (itt == S.end() ? -1 : itt -> second);
    }
    for(i=1; i<=lg; ++i)
        for(j=0; j<n; ++j)
            if(go[i-1][j] == -1) go[i][j] = -1;
                else go[i][j] = go[i-1][go[i-1][j]];

    bad.clear();
}

int solve(int pos)
{
    int i, ans = 0, lim;

    ///
    set<int> :: iterator it;
    set<Pair> :: iterator sk;
    ///

    it = bad.lower_bound(where[pos]);
    if(it == bad.end()) lim = inf;
        else lim = *it;

    while(where[pos] == lim || (go[0][pos] != -1 && where[go[0][pos]] >= lim) || (go[0][pos] == -1 && lim < inf))
    {
        sk = S.upper_bound({ where[pos] + L, inf });
        if(sk == S.end()) return ans;

        ++ans;

        pos = sk->second;

        it = bad.lower_bound(where[pos]);
        if(it == bad.end()) lim = inf;
            else lim = *it;
    }

    for(i=lg; i>=0; --i)
        if(go[i][pos] != -1 && where[go[i][pos]] < lim)
            pos = go[i][pos], ans += (1<<i);

    if(go[0][pos] == -1 && lim == inf) return ans;
    return ans + solve(pos);
}

int solve2()
{
    set<Pair> :: iterator it;
    it = S.begin();

    int ans = 0;

    while(it != S.end())
    {
        it = S.upper_bound({ it->first + L, inf });
        ++ans;
    }
    return ans;
}

int update(int id, int y)
{
    if(nr_upd % BS == 0) refresh_all();
    ++nr_upd;

    bad.insert(where[id]);
    bad.insert(y);

 //   for(auto it : bad) cerr << it << ' '; cerr << '\n';

    S.erase(S.find({ where[id], id }));
    S.insert({ y, id }); where[id] = y;


    int curr = solve(S.begin() -> second) + 1;

 //   cerr << curr << ' ' << solve2() << '\n';
    return curr;
}

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct

Subtask #2
0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Execution timed out 9020 ms 512 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Execution timed out 9020 ms 512 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Execution timed out 9020 ms 512 KB Time limit exceeded
5 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Execution timed out 9020 ms 512 KB Time limit exceeded
5 Halted 0 ms 0 KB -