oj.uz

Submission #423406

# Submission time Handle Problem Language Result Execution time Memory
423406 2021-06-11T05:24:20 Z arayi Dancing Elephants (IOI11_elephants) C++17
26 / 100
 9000 ms 5608 KB 
#include "elephants.h"
#include <bits/stdc++.h>
#include <set>
#define MP make_pair
using namespace std;

const int N = 1e6 + 30;
int n, l;
set <pair<int, int> > fp;
int x[N], fr, sc;
int haj[N], nax[N];
void rmv(int i)
{
    if(i != fr && i != sc)
    {
        nax[haj[i]]= nax[i];
        haj[nax[i]] = haj[i];
    }
    fp.erase(MP(x[i], i));
    auto i1 = fp.end();
    fr = (*fp.begin()).second, sc = (*(--i1)).second;
}
void add(int i)
{
    auto i1 = fp.lower_bound(MP(x[i], i));
    if(i1 != fp.end()) nax[(*i1).second] = i, haj[i] = (*i1).second;
    if(i1 != fp.begin()) haj[(*(--i1)).second] = i, nax[i] = (*i1).second;
    fp.insert(MP(x[i], i));
    i1 = fp.end();
    fr = (*fp.begin()).second, sc = (*(--i1)).second;
}
int go()
{
    int v = fr, sm = 0, nx = -l - 1;
    while(1)
    {
        if(x[v] > nx + l) nx = x[v], sm++;
        if(v == sc) break;
        v = haj[v];
    }
    return sm;
}
void init(int N, int L, int X[])
{
    n=N, l=L;
    for(int i = 0; i < n; i++)
    {
        x[i] = X[i];
        add(i);
    }
}

int update(int i, int y)
{
    rmv(i);
    x[i] = y;
    add(i);
    return go();
}

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

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

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 276 KB Output is correct
7 Correct 3280 ms 2592 KB Output is correct
8 Correct 4826 ms 3020 KB Output is correct
9 Correct 7412 ms 5608 KB Output is correct
10 Correct 7459 ms 5376 KB Output is correct
11 Correct 7354 ms 5320 KB Output is correct
12 Execution timed out 9037 ms 5444 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 276 KB Output is correct
7 Correct 3280 ms 2592 KB Output is correct
8 Correct 4826 ms 3020 KB Output is correct
9 Correct 7412 ms 5608 KB Output is correct
10 Correct 7459 ms 5376 KB Output is correct
11 Correct 7354 ms 5320 KB Output is correct
12 Execution timed out 9037 ms 5444 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 332 KB Output is correct
2 Correct 1 ms 332 KB Output is correct
3 Correct 1 ms 332 KB Output is correct
4 Correct 1 ms 332 KB Output is correct
5 Correct 1 ms 332 KB Output is correct
6 Correct 1 ms 276 KB Output is correct
7 Correct 3280 ms 2592 KB Output is correct
8 Correct 4826 ms 3020 KB Output is correct
9 Correct 7412 ms 5608 KB Output is correct
10 Correct 7459 ms 5376 KB Output is correct
11 Correct 7354 ms 5320 KB Output is correct
12 Execution timed out 9037 ms 5444 KB Time limit exceeded
13 Halted 0 ms 0 KB -