oj.uz

Submission #423431

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

const int N = 1e5 + 30;
int n, l;
set <pair<int, int> > fp;
int x[N], fr, sc;
int haj[N], nax[N], h[N];
void rmv(int i)
{
    bool bl = 0;
    if(i != fr && i != sc)
    {
        nax[haj[i]]= nax[i];
        haj[nax[i]] = haj[i];
        bl = 1;
    }
    fp.erase(MP(x[i], i));
    auto i1 = fp.end();
    fr = (*fp.begin()).second, sc = (*(--i1)).second;
    if(bl)
    {
        int v = i;
        while(v != fr)
        {
            v = nax[v];
            if(x[v] + l < x[nax[i]]) break;
            if(x[v] + l < x[haj[i]]) h[v] = haj[i];
        }
    }
}
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;
    i1 = fp.lower_bound(MP(x[i] + l + 1, -1));
    if(i1 != fp.end()) h[i] = (*i1).second;
    int v = i;
    while(v != fr)
    {
        v = nax[v];
        if(x[v] + l < x[nax[i]]) break;
        if(x[v] + l < x[i]) h[v] = i;
    }
}
int go()
{
    int v = fr, sm = 1, nx = x[fr] + l;
    while(nx < x[sc])
    {
        sm++; v = h[v]; nx = x[v] + l;
    }
    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];
        if(n <= 50000) 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 384 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 384 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 332 KB Output is correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 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 332 KB Output is correct
7 Correct 1249 ms 1732 KB Output is correct
8 Correct 1749 ms 2064 KB Output is correct
9 Correct 3828 ms 4236 KB Output is correct
10 Correct 3817 ms 4232 KB Output is correct
11 Correct 2118 ms 4224 KB Output is correct
12 Execution timed out 9067 ms 4164 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 384 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 332 KB Output is correct
7 Correct 1249 ms 1732 KB Output is correct
8 Correct 1749 ms 2064 KB Output is correct
9 Correct 3828 ms 4236 KB Output is correct
10 Correct 3817 ms 4232 KB Output is correct
11 Correct 2118 ms 4224 KB Output is correct
12 Execution timed out 9067 ms 4164 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 384 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 332 KB Output is correct
7 Correct 1249 ms 1732 KB Output is correct
8 Correct 1749 ms 2064 KB Output is correct
9 Correct 3828 ms 4236 KB Output is correct
10 Correct 3817 ms 4232 KB Output is correct
11 Correct 2118 ms 4224 KB Output is correct
12 Execution timed out 9067 ms 4164 KB Time limit exceeded
13 Halted 0 ms 0 KB -