oj.uz

Submission #171374

# Submission time Handle Problem Language Result Execution time Memory
171374 2019-12-28T12:03:24 Z arnold518 Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 11612 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 = 390;
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 372 KB Output is correct
2 Correct 0 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 372 KB Output is correct
2 Correct 0 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 372 KB Output is correct
2 Correct 0 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 2475 ms 1796 KB Output is correct
8 Correct 2557 ms 2168 KB Output is correct
9 Correct 2860 ms 4108 KB Output is correct
10 Correct 1986 ms 4216 KB Output is correct
11 Correct 1883 ms 4112 KB Output is correct
12 Correct 4501 ms 4344 KB Output is correct
13 Correct 1747 ms 4124 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 372 KB Output is correct
2 Correct 0 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 2475 ms 1796 KB Output is correct
8 Correct 2557 ms 2168 KB Output is correct
9 Correct 2860 ms 4108 KB Output is correct
10 Correct 1986 ms 4216 KB Output is correct
11 Correct 1883 ms 4112 KB Output is correct
12 Correct 4501 ms 4344 KB Output is correct
13 Correct 1747 ms 4124 KB Output is correct
14 Correct 3644 ms 2560 KB Output is correct
15 Correct 3928 ms 2708 KB Output is correct
16 Correct 6179 ms 4344 KB Output is correct
17 Correct 6990 ms 5736 KB Output is correct
18 Correct 6916 ms 5752 KB Output is correct
19 Correct 6560 ms 5628 KB Output is correct
20 Correct 6860 ms 5852 KB Output is correct
21 Correct 6984 ms 5764 KB Output is correct
22 Correct 3245 ms 5644 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 372 KB Output is correct
2 Correct 0 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 2475 ms 1796 KB Output is correct
8 Correct 2557 ms 2168 KB Output is correct
9 Correct 2860 ms 4108 KB Output is correct
10 Correct 1986 ms 4216 KB Output is correct
11 Correct 1883 ms 4112 KB Output is correct
12 Correct 4501 ms 4344 KB Output is correct
13 Correct 1747 ms 4124 KB Output is correct
14 Correct 3644 ms 2560 KB Output is correct
15 Correct 3928 ms 2708 KB Output is correct
16 Correct 6179 ms 4344 KB Output is correct
17 Correct 6990 ms 5736 KB Output is correct
18 Correct 6916 ms 5752 KB Output is correct
19 Correct 6560 ms 5628 KB Output is correct
20 Correct 6860 ms 5852 KB Output is correct
21 Correct 6984 ms 5764 KB Output is correct
22 Correct 3245 ms 5644 KB Output is correct
23 Execution timed out 9041 ms 11612 KB Time limit exceeded
24 Halted 0 ms 0 KB -