oj.uz

Submission #423409

# Submission time Handle Problem Language Result Execution time Memory
423409 2021-06-11T05:31:20 Z arayi Dancing Elephants (IOI11_elephants) C++17
26 / 100
 9000 ms 4048 KB 
#include "elephants.h"
#include <bits/stdc++.h>
#include <set>
#define MP make_pair
#pragma GCC optimize("O2")
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 = 1, nx = x[fr] + l;
    while(nx < x[sc])
    {
        while(x[v] <= nx) v = haj[v];
        sm++, 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];
        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 332 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 332 KB Output is correct
7 Correct 3651 ms 1688 KB Output is correct
8 Correct 5076 ms 2000 KB Output is correct
9 Correct 7098 ms 4040 KB Output is correct
10 Correct 7262 ms 4044 KB Output is correct
11 Correct 7266 ms 4048 KB Output is correct
12 Execution timed out 9026 ms 4032 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 332 KB Output is correct
7 Correct 3651 ms 1688 KB Output is correct
8 Correct 5076 ms 2000 KB Output is correct
9 Correct 7098 ms 4040 KB Output is correct
10 Correct 7262 ms 4044 KB Output is correct
11 Correct 7266 ms 4048 KB Output is correct
12 Execution timed out 9026 ms 4032 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 332 KB Output is correct
7 Correct 3651 ms 1688 KB Output is correct
8 Correct 5076 ms 2000 KB Output is correct
9 Correct 7098 ms 4040 KB Output is correct
10 Correct 7262 ms 4044 KB Output is correct
11 Correct 7266 ms 4048 KB Output is correct
12 Execution timed out 9026 ms 4032 KB Time limit exceeded
13 Halted 0 ms 0 KB -