oj.uz

Submission #171318

# Submission time Handle Problem Language Result Execution time Memory
171318 2019-12-28T10:51:23 Z arnold518 Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 10460 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 = 480;

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 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 3 ms 376 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 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 3 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2914 ms 1700 KB Output is correct
8 Correct 3025 ms 1784 KB Output is correct
9 Correct 3437 ms 3772 KB Output is correct
10 Correct 1879 ms 3768 KB Output is correct
11 Correct 1835 ms 3704 KB Output is correct
12 Correct 4676 ms 3764 KB Output is correct
13 Correct 1745 ms 3760 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 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2914 ms 1700 KB Output is correct
8 Correct 3025 ms 1784 KB Output is correct
9 Correct 3437 ms 3772 KB Output is correct
10 Correct 1879 ms 3768 KB Output is correct
11 Correct 1835 ms 3704 KB Output is correct
12 Correct 4676 ms 3764 KB Output is correct
13 Correct 1745 ms 3760 KB Output is correct
14 Correct 3766 ms 2216 KB Output is correct
15 Correct 4643 ms 2532 KB Output is correct
16 Correct 6652 ms 3996 KB Output is correct
17 Correct 7446 ms 5096 KB Output is correct
18 Correct 7241 ms 5212 KB Output is correct
19 Correct 8575 ms 5112 KB Output is correct
20 Correct 7368 ms 5224 KB Output is correct
21 Correct 7230 ms 5212 KB Output is correct
22 Correct 4637 ms 5124 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 2 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 2914 ms 1700 KB Output is correct
8 Correct 3025 ms 1784 KB Output is correct
9 Correct 3437 ms 3772 KB Output is correct
10 Correct 1879 ms 3768 KB Output is correct
11 Correct 1835 ms 3704 KB Output is correct
12 Correct 4676 ms 3764 KB Output is correct
13 Correct 1745 ms 3760 KB Output is correct
14 Correct 3766 ms 2216 KB Output is correct
15 Correct 4643 ms 2532 KB Output is correct
16 Correct 6652 ms 3996 KB Output is correct
17 Correct 7446 ms 5096 KB Output is correct
18 Correct 7241 ms 5212 KB Output is correct
19 Correct 8575 ms 5112 KB Output is correct
20 Correct 7368 ms 5224 KB Output is correct
21 Correct 7230 ms 5212 KB Output is correct
22 Correct 4637 ms 5124 KB Output is correct
23 Execution timed out 9061 ms 10460 KB Time limit exceeded
24 Halted 0 ms 0 KB -