oj.uz

Submission #171317

# Submission time Handle Problem Language Result Execution time Memory
171317 2019-12-28T10:49:45 Z arnold518 Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 15452 KB 
#include "elephants.h"
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 150000;
const int SQ = 380;

int N, L, A[MAXN+10], B[MAXN+10], S[MAXN+10];
pii C[MAXN+10];

int P[MAXN/SQ+10][SQ*3+10], Q[MAXN/SQ+10][SQ*3+10], R[MAXN/SQ+10][SQ*3+10], sz[MAXN/SQ+10];

void calc(int num)
{
    int i, j;
    sort(P[num], P[num]+sz[num]);
    for(i=0; i<=sz[num]; i++) Q[num][i]=R[num][i]=0;
    for(i=sz[num]-1; i>=0; i--)
    {
        int pos=upper_bound(P[num], P[num]+sz[num], P[num][i]+L)-P[num];
        if(pos==sz[num]) Q[num][i]=P[num][i]+L, R[num][i]=1;
        else Q[num][i]=Q[num][pos], R[num][i]=R[num][pos]+1;
    }
    S[num]=P[num][0];
}

void make()
{
    int i, j;
    for(i=0; i<N; i++) C[i]={A[i], i};
    sort(C, C+N);
    for(i=0; i<=(N-1)/SQ; i++) sz[i]=0;
    for(i=0; i<N; i++) P[i/SQ][sz[i/SQ]++]=C[i].first, B[C[i].second]=i/SQ;
    for(i=0; i<=(N-1)/SQ; i++) calc(i);
}

void pop(int p)
{
    int i, j;

    int num=B[p];
    for(i=0; i<sz[num]; i++) if(P[num][i]==A[p]) break;
    int pos=i;
    for(i=pos+1; i<sz[num]; i++) P[num][i-1]=P[num][i];
    sz[num]--;
    calc(num);

    B[p]=-1;
}

void push(int p, int x)
{
    int i, j;

    int num=upper_bound(S, S+(N-1)/SQ+1, x)-S-1;
    if(num==-1) num=0;
    P[num][sz[num]++]=x;
    calc(num);

    B[p]=num;
}

void init(int _N, int _L, int *X)
{
    int i, j;
    N=_N; L=_L;

    for(i=0; i<N; i++) A[i]=X[i];
    make();
}

int query()
{
    int i, j;
    int bef=-1;
    int ans=0;
    for(i=0; i<=(N-1)/SQ; i++)
    {
        int pos=upper_bound(P[i], P[i]+sz[i], bef)-P[i];
        if(pos==sz[i]) continue;
        ans+=R[i][pos];
        bef=Q[i][pos];
    }
    return ans;
}

int qcnt=0;

int update(int p, int y)
{
    int i, j;

    pop(p);
    push(p, y);
    A[p]=y;

    qcnt++;
    if(qcnt==SQ) qcnt=0, make();

    return query();
}

Compilation message

elephants.cpp: In function 'void calc(int)':
elephants.cpp:19:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
elephants.cpp: In function 'void make()':
elephants.cpp:33:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
elephants.cpp: In function 'void pop(int)':
elephants.cpp:43:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
elephants.cpp: In function 'void push(int, int)':
elephants.cpp:57:9: warning: unused variable 'i' [-Wunused-variable]
     int i, j;
         ^
elephants.cpp:57:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
elephants.cpp: In function 'void init(int, int, int*)':
elephants.cpp:69:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
elephants.cpp: In function 'int query()':
elephants.cpp:78:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:95:9: warning: unused variable 'i' [-Wunused-variable]
     int i, j;
         ^
elephants.cpp:95:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^

Subtask #1
10.0 / 10.0

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

Subtask #2
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 0 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 380 KB Output is correct
5 Correct 3 ms 380 KB Output is correct
6 Correct 2 ms 376 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 0 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 380 KB Output is correct
5 Correct 3 ms 380 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2033 ms 1712 KB Output is correct
8 Correct 2149 ms 1980 KB Output is correct
9 Correct 2412 ms 3804 KB Output is correct
10 Correct 2056 ms 3816 KB Output is correct
11 Correct 2130 ms 3772 KB Output is correct
12 Correct 3841 ms 3832 KB Output is correct
13 Correct 1958 ms 4920 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 0 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 380 KB Output is correct
5 Correct 3 ms 380 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2033 ms 1712 KB Output is correct
8 Correct 2149 ms 1980 KB Output is correct
9 Correct 2412 ms 3804 KB Output is correct
10 Correct 2056 ms 3816 KB Output is correct
11 Correct 2130 ms 3772 KB Output is correct
12 Correct 3841 ms 3832 KB Output is correct
13 Correct 1958 ms 4920 KB Output is correct
14 Correct 3086 ms 3752 KB Output is correct
15 Correct 3364 ms 3968 KB Output is correct
16 Correct 5642 ms 5832 KB Output is correct
17 Correct 6383 ms 7164 KB Output is correct
18 Correct 6412 ms 7160 KB Output is correct
19 Correct 7034 ms 7316 KB Output is correct
20 Correct 6278 ms 7160 KB Output is correct
21 Correct 6141 ms 7124 KB Output is correct
22 Correct 2493 ms 6764 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 0 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 380 KB Output is correct
5 Correct 3 ms 380 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2033 ms 1712 KB Output is correct
8 Correct 2149 ms 1980 KB Output is correct
9 Correct 2412 ms 3804 KB Output is correct
10 Correct 2056 ms 3816 KB Output is correct
11 Correct 2130 ms 3772 KB Output is correct
12 Correct 3841 ms 3832 KB Output is correct
13 Correct 1958 ms 4920 KB Output is correct
14 Correct 3086 ms 3752 KB Output is correct
15 Correct 3364 ms 3968 KB Output is correct
16 Correct 5642 ms 5832 KB Output is correct
17 Correct 6383 ms 7164 KB Output is correct
18 Correct 6412 ms 7160 KB Output is correct
19 Correct 7034 ms 7316 KB Output is correct
20 Correct 6278 ms 7160 KB Output is correct
21 Correct 6141 ms 7124 KB Output is correct
22 Correct 2493 ms 6764 KB Output is correct
23 Execution timed out 9036 ms 15452 KB Time limit exceeded
24 Halted 0 ms 0 KB -