Submission #171366

# Submission time Handle Problem Language Result Execution time Memory
171366 2019-12-28T11:43:44 Z arnold518 Dancing Elephants (IOI11_elephants) C++14
97 / 100
9000 ms 12380 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;
const int SQ2 = 300;

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

int P[MAXN/SQ+10][SQ+SQ2+10], Q[MAXN/SQ+10][SQ+SQ2+10], R[MAXN/SQ+10][SQ+SQ2+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: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;
            ^
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 248 KB Output is correct
3 Correct 0 ms 248 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 248 KB Output is correct
3 Correct 0 ms 248 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
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 248 KB Output is correct
3 Correct 0 ms 248 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 454 ms 1864 KB Output is correct
8 Correct 541 ms 2200 KB Output is correct
9 Correct 965 ms 4396 KB Output is correct
10 Correct 1459 ms 4404 KB Output is correct
11 Correct 1542 ms 4344 KB Output is correct
12 Correct 1755 ms 4344 KB Output is correct
13 Correct 1416 ms 4472 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 248 KB Output is correct
3 Correct 0 ms 248 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 454 ms 1864 KB Output is correct
8 Correct 541 ms 2200 KB Output is correct
9 Correct 965 ms 4396 KB Output is correct
10 Correct 1459 ms 4404 KB Output is correct
11 Correct 1542 ms 4344 KB Output is correct
12 Correct 1755 ms 4344 KB Output is correct
13 Correct 1416 ms 4472 KB Output is correct
14 Correct 954 ms 2444 KB Output is correct
15 Correct 989 ms 2936 KB Output is correct
16 Correct 2610 ms 4600 KB Output is correct
17 Correct 3527 ms 6008 KB Output is correct
18 Correct 3619 ms 5984 KB Output is correct
19 Correct 3391 ms 5984 KB Output is correct
20 Correct 3557 ms 6108 KB Output is correct
21 Correct 3446 ms 5984 KB Output is correct
22 Correct 2628 ms 6008 KB Output is correct
# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 4 ms 248 KB Output is correct
3 Correct 0 ms 248 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 454 ms 1864 KB Output is correct
8 Correct 541 ms 2200 KB Output is correct
9 Correct 965 ms 4396 KB Output is correct
10 Correct 1459 ms 4404 KB Output is correct
11 Correct 1542 ms 4344 KB Output is correct
12 Correct 1755 ms 4344 KB Output is correct
13 Correct 1416 ms 4472 KB Output is correct
14 Correct 954 ms 2444 KB Output is correct
15 Correct 989 ms 2936 KB Output is correct
16 Correct 2610 ms 4600 KB Output is correct
17 Correct 3527 ms 6008 KB Output is correct
18 Correct 3619 ms 5984 KB Output is correct
19 Correct 3391 ms 5984 KB Output is correct
20 Correct 3557 ms 6108 KB Output is correct
21 Correct 3446 ms 5984 KB Output is correct
22 Correct 2628 ms 6008 KB Output is correct
23 Execution timed out 9084 ms 12380 KB Time limit exceeded
24 Halted 0 ms 0 KB -