oj.uz

Submission #97227

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

using namespace std;

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

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

Subtask #2
16.0 / 16.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 710 ms 2660 KB Output is correct
8 Correct 1033 ms 3280 KB Output is correct
9 Correct 3283 ms 7388 KB Output is correct
10 Correct 2841 ms 7388 KB Output is correct
11 Correct 3148 ms 7380 KB Output is correct
12 Correct 7825 ms 7380 KB Output is correct
13 Correct 2879 ms 8516 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 384 KB Output is correct
2 Correct 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 710 ms 2660 KB Output is correct
8 Correct 1033 ms 3280 KB Output is correct
9 Correct 3283 ms 7388 KB Output is correct
10 Correct 2841 ms 7388 KB Output is correct
11 Correct 3148 ms 7380 KB Output is correct
12 Correct 7825 ms 7380 KB Output is correct
13 Correct 2879 ms 8516 KB Output is correct
14 Correct 2599 ms 5044 KB Output is correct
15 Correct 1891 ms 5880 KB Output is correct
16 Execution timed out 9053 ms 9336 KB Time limit exceeded
17 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 3 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 512 KB Output is correct
5 Correct 3 ms 512 KB Output is correct
6 Correct 2 ms 512 KB Output is correct
7 Correct 710 ms 2660 KB Output is correct
8 Correct 1033 ms 3280 KB Output is correct
9 Correct 3283 ms 7388 KB Output is correct
10 Correct 2841 ms 7388 KB Output is correct
11 Correct 3148 ms 7380 KB Output is correct
12 Correct 7825 ms 7380 KB Output is correct
13 Correct 2879 ms 8516 KB Output is correct
14 Correct 2599 ms 5044 KB Output is correct
15 Correct 1891 ms 5880 KB Output is correct
16 Execution timed out 9053 ms 9336 KB Time limit exceeded
17 Halted 0 ms 0 KB -