oj.uz

Submission #171377

# Submission time Handle Problem Language Result Execution time Memory
171377 2019-12-28T12:29:14 Z arnold518 Dancing Elephants (IOI11_elephants) C++14
50 / 100
 9000 ms 5412 KB 
#pragma GCC optimize("O3")
#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#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 = 500;
int SQ2 = 400;

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

int P[MAXN/SQ+10][SQ*10+10], Q[MAXN/SQ+10][SQ*10+10], R[MAXN/SQ+10][SQ*10+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; SQ2=sqrt(N)+1;

    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==SQ2) qcnt=0, make();

    return query();
}

Compilation message

elephants.cpp: In function 'void calc(int)':
elephants.cpp:23:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
elephants.cpp: In function 'void make()':
elephants.cpp:37:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
elephants.cpp: In function 'void pop(int)':
elephants.cpp:47:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
elephants.cpp: In function 'void push(int, int)':
elephants.cpp:61:9: warning: unused variable 'i' [-Wunused-variable]
     int i, j;
         ^
elephants.cpp:61:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
elephants.cpp: In function 'void init(int, int, int*)':
elephants.cpp:73:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
elephants.cpp: In function 'int query()':
elephants.cpp:82:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:99:9: warning: unused variable 'i' [-Wunused-variable]
     int i, j;
         ^
elephants.cpp:99: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 348 KB Output is correct
2 Correct 2 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 348 KB Output is correct
2 Correct 2 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 376 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 348 KB Output is correct
2 Correct 2 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 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3614 ms 1768 KB Output is correct
8 Correct 3680 ms 2000 KB Output is correct
9 Correct 4041 ms 3792 KB Output is correct
10 Correct 3970 ms 3804 KB Output is correct
11 Correct 3436 ms 3796 KB Output is correct
12 Correct 5449 ms 3840 KB Output is correct
13 Correct 3980 ms 3928 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 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 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3614 ms 1768 KB Output is correct
8 Correct 3680 ms 2000 KB Output is correct
9 Correct 4041 ms 3792 KB Output is correct
10 Correct 3970 ms 3804 KB Output is correct
11 Correct 3436 ms 3796 KB Output is correct
12 Correct 5449 ms 3840 KB Output is correct
13 Correct 3980 ms 3928 KB Output is correct
14 Correct 5232 ms 2528 KB Output is correct
15 Correct 5582 ms 2808 KB Output is correct
16 Correct 7682 ms 4168 KB Output is correct
17 Correct 8617 ms 5288 KB Output is correct
18 Correct 8183 ms 5412 KB Output is correct
19 Execution timed out 9010 ms 5368 KB Time limit exceeded
20 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 348 KB Output is correct
2 Correct 2 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 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 3614 ms 1768 KB Output is correct
8 Correct 3680 ms 2000 KB Output is correct
9 Correct 4041 ms 3792 KB Output is correct
10 Correct 3970 ms 3804 KB Output is correct
11 Correct 3436 ms 3796 KB Output is correct
12 Correct 5449 ms 3840 KB Output is correct
13 Correct 3980 ms 3928 KB Output is correct
14 Correct 5232 ms 2528 KB Output is correct
15 Correct 5582 ms 2808 KB Output is correct
16 Correct 7682 ms 4168 KB Output is correct
17 Correct 8617 ms 5288 KB Output is correct
18 Correct 8183 ms 5412 KB Output is correct
19 Execution timed out 9010 ms 5368 KB Time limit exceeded
20 Halted 0 ms 0 KB -