oj.uz

Submission #171375

# Submission time Handle Problem Language Result Execution time Memory
171375 2019-12-28T12:05:42 Z arnold518 Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 22864 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 = 100;
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 504 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 504 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 504 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 627 ms 2736 KB Output is correct
8 Correct 707 ms 3448 KB Output is correct
9 Correct 1098 ms 7932 KB Output is correct
10 Correct 1589 ms 7936 KB Output is correct
11 Correct 1605 ms 8056 KB Output is correct
12 Correct 2226 ms 7928 KB Output is correct
13 Correct 1635 ms 8028 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 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 627 ms 2736 KB Output is correct
8 Correct 707 ms 3448 KB Output is correct
9 Correct 1098 ms 7932 KB Output is correct
10 Correct 1589 ms 7936 KB Output is correct
11 Correct 1605 ms 8056 KB Output is correct
12 Correct 2226 ms 7928 KB Output is correct
13 Correct 1635 ms 8028 KB Output is correct
14 Correct 1325 ms 3688 KB Output is correct
15 Correct 1248 ms 4472 KB Output is correct
16 Correct 3246 ms 8168 KB Output is correct
17 Correct 4586 ms 10936 KB Output is correct
18 Correct 4378 ms 10972 KB Output is correct
19 Correct 3872 ms 10972 KB Output is correct
20 Correct 4336 ms 10944 KB Output is correct
21 Correct 4254 ms 10940 KB Output is correct
22 Correct 3232 ms 10872 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 504 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 627 ms 2736 KB Output is correct
8 Correct 707 ms 3448 KB Output is correct
9 Correct 1098 ms 7932 KB Output is correct
10 Correct 1589 ms 7936 KB Output is correct
11 Correct 1605 ms 8056 KB Output is correct
12 Correct 2226 ms 7928 KB Output is correct
13 Correct 1635 ms 8028 KB Output is correct
14 Correct 1325 ms 3688 KB Output is correct
15 Correct 1248 ms 4472 KB Output is correct
16 Correct 3246 ms 8168 KB Output is correct
17 Correct 4586 ms 10936 KB Output is correct
18 Correct 4378 ms 10972 KB Output is correct
19 Correct 3872 ms 10972 KB Output is correct
20 Correct 4336 ms 10944 KB Output is correct
21 Correct 4254 ms 10940 KB Output is correct
22 Correct 3232 ms 10872 KB Output is correct
23 Execution timed out 9024 ms 22864 KB Time limit exceeded
24 Halted 0 ms 0 KB -