oj.uz

Submission #97224

# Submission time Handle Problem Language Result Execution time Memory
97224 2019-02-14T13:18:51 Z Alexa2001 Dancing Elephants (IOI11_elephants) C++17
26 / 100
 9000 ms 8948 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];
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 3 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 4 ms 512 KB Output is correct

Subtask #2
16.0 / 16.0

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

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 538 ms 2800 KB Output is correct
8 Correct 679 ms 4216 KB Output is correct
9 Correct 3282 ms 8948 KB Output is correct
10 Correct 1053 ms 8824 KB Output is correct
11 Correct 1631 ms 8824 KB Output is correct
12 Execution timed out 9037 ms 8824 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 538 ms 2800 KB Output is correct
8 Correct 679 ms 4216 KB Output is correct
9 Correct 3282 ms 8948 KB Output is correct
10 Correct 1053 ms 8824 KB Output is correct
11 Correct 1631 ms 8824 KB Output is correct
12 Execution timed out 9037 ms 8824 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 512 KB Output is correct
2 Correct 3 ms 512 KB Output is correct
3 Correct 4 ms 512 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 2 ms 384 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 538 ms 2800 KB Output is correct
8 Correct 679 ms 4216 KB Output is correct
9 Correct 3282 ms 8948 KB Output is correct
10 Correct 1053 ms 8824 KB Output is correct
11 Correct 1631 ms 8824 KB Output is correct
12 Execution timed out 9037 ms 8824 KB Time limit exceeded
13 Halted 0 ms 0 KB -