oj.uz

Submission #171331

# Submission time Handle Problem Language Result Execution time Memory
171331 2019-12-28T11:03:32 Z arnold518 Dancing Elephants (IOI11_elephants) C++14
50 / 100
 9000 ms 3704 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 = 700;
const 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*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==SQ2) qcnt=0, make();

    return query();
}

Compilation message

elephants.cpp: In function 'void calc(int)':
elephants.cpp:20:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
elephants.cpp: In function 'void make()':
elephants.cpp:34:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
elephants.cpp: In function 'void pop(int)':
elephants.cpp:44:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
elephants.cpp: In function 'void push(int, int)':
elephants.cpp:58:9: warning: unused variable 'i' [-Wunused-variable]
     int i, j;
         ^
elephants.cpp:58:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
elephants.cpp: In function 'void init(int, int, int*)':
elephants.cpp:70:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
elephants.cpp: In function 'int query()':
elephants.cpp:79:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:96:9: warning: unused variable 'i' [-Wunused-variable]
     int i, j;
         ^
elephants.cpp:96: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 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 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 4 ms 504 KB Output is correct
6 Correct 6 ms 504 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 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 4 ms 504 KB Output is correct
6 Correct 6 ms 504 KB Output is correct
7 Correct 5030 ms 1632 KB Output is correct
8 Correct 5226 ms 1856 KB Output is correct
9 Correct 5813 ms 3448 KB Output is correct
10 Correct 3517 ms 3440 KB Output is correct
11 Correct 2815 ms 3548 KB Output is correct
12 Correct 6653 ms 3460 KB Output is correct
13 Correct 3399 ms 3448 KB Output is correct

Subtask #4
0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 4 ms 504 KB Output is correct
6 Correct 6 ms 504 KB Output is correct
7 Correct 5030 ms 1632 KB Output is correct
8 Correct 5226 ms 1856 KB Output is correct
9 Correct 5813 ms 3448 KB Output is correct
10 Correct 3517 ms 3440 KB Output is correct
11 Correct 2815 ms 3548 KB Output is correct
12 Correct 6653 ms 3460 KB Output is correct
13 Correct 3399 ms 3448 KB Output is correct
14 Correct 6174 ms 2372 KB Output is correct
15 Correct 7454 ms 2396 KB Output is correct
16 Execution timed out 9038 ms 3704 KB Time limit exceeded
17 Halted 0 ms 0 KB -

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 4 ms 504 KB Output is correct
6 Correct 6 ms 504 KB Output is correct
7 Correct 5030 ms 1632 KB Output is correct
8 Correct 5226 ms 1856 KB Output is correct
9 Correct 5813 ms 3448 KB Output is correct
10 Correct 3517 ms 3440 KB Output is correct
11 Correct 2815 ms 3548 KB Output is correct
12 Correct 6653 ms 3460 KB Output is correct
13 Correct 3399 ms 3448 KB Output is correct
14 Correct 6174 ms 2372 KB Output is correct
15 Correct 7454 ms 2396 KB Output is correct
16 Execution timed out 9038 ms 3704 KB Time limit exceeded
17 Halted 0 ms 0 KB -