oj.uz

답안 #423412

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
423412 2021-06-11T05:32:37 Z arayi 코끼리 (Dancing Elephants) (IOI11_elephants) C++17
26 / 100
 9000 ms 4052 KB 
#include "elephants.h"
#include <bits/stdc++.h>
#include <set>
#define MP make_pair
#pragma GCC optimize("Os")
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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 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 3906 ms 1696 KB Output is correct
8 Correct 5508 ms 2004 KB Output is correct
9 Correct 7839 ms 4036 KB Output is correct
10 Correct 7771 ms 4052 KB Output is correct
11 Correct 7493 ms 4048 KB Output is correct
12 Execution timed out 9080 ms 4040 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #4
0 / 47.0

# 결과 실행 시간 메모리 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 3906 ms 1696 KB Output is correct
8 Correct 5508 ms 2004 KB Output is correct
9 Correct 7839 ms 4036 KB Output is correct
10 Correct 7771 ms 4052 KB Output is correct
11 Correct 7493 ms 4048 KB Output is correct
12 Execution timed out 9080 ms 4040 KB Time limit exceeded
13 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 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 3906 ms 1696 KB Output is correct
8 Correct 5508 ms 2004 KB Output is correct
9 Correct 7839 ms 4036 KB Output is correct
10 Correct 7771 ms 4052 KB Output is correct
11 Correct 7493 ms 4048 KB Output is correct
12 Execution timed out 9080 ms 4040 KB Time limit exceeded
13 Halted 0 ms 0 KB -