oj.uz

Submission #97226

# Submission time Handle Problem Language Result Execution time Memory
97226 2019-02-14T13:26:57 Z Alexa2001 Dancing Elephants (IOI11_elephants) C++17
26 / 100
 9000 ms 7416 KB 
#include "elephants.h"
#include <bits/stdc++.h>

using namespace std;

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

typedef pair<int,int> Pair;

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

int go[lg+2][Nmax];
int prevpos;

bool active[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]];

    for(i=0; i<n; ++i) active[i] = 1;
    bad.clear();
}

int solve(int pos)
{
    assert(pos != prevpos);
    prevpos = 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 && active[go[0][pos]] && where[go[0][pos]] >= lim) || (go[0][pos] != -1 && !active[go[0][pos]])|| (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 && active[go[i][pos]])
            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;

    active[id] = 0;
    prevpos = -1;

    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 0 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 550 ms 2660 KB Output is correct
8 Correct 756 ms 3292 KB Output is correct
9 Correct 2848 ms 7260 KB Output is correct
10 Correct 1574 ms 7416 KB Output is correct
11 Correct 1887 ms 7392 KB Output is correct
12 Execution timed out 9033 ms 7288 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 550 ms 2660 KB Output is correct
8 Correct 756 ms 3292 KB Output is correct
9 Correct 2848 ms 7260 KB Output is correct
10 Correct 1574 ms 7416 KB Output is correct
11 Correct 1887 ms 7392 KB Output is correct
12 Execution timed out 9033 ms 7288 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 2 ms 384 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 384 KB Output is correct
6 Correct 3 ms 384 KB Output is correct
7 Correct 550 ms 2660 KB Output is correct
8 Correct 756 ms 3292 KB Output is correct
9 Correct 2848 ms 7260 KB Output is correct
10 Correct 1574 ms 7416 KB Output is correct
11 Correct 1887 ms 7392 KB Output is correct
12 Execution timed out 9033 ms 7288 KB Time limit exceeded
13 Halted 0 ms 0 KB -