oj.uz

Submission #171322

# Submission time Handle Problem Language Result Execution time Memory
171322 2019-12-28T10:54:13 Z arnold518 Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 10424 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 = 200;

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 1 ms 376 KB Output is correct
3 Correct 3 ms 380 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 1 ms 376 KB Output is correct
3 Correct 3 ms 380 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 14 ms 352 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 1 ms 376 KB Output is correct
3 Correct 3 ms 380 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 14 ms 352 KB Output is correct
7 Correct 931 ms 1716 KB Output is correct
8 Correct 1133 ms 1912 KB Output is correct
9 Correct 1687 ms 3704 KB Output is correct
10 Correct 1826 ms 3800 KB Output is correct
11 Correct 1846 ms 3796 KB Output is correct
12 Correct 2932 ms 3832 KB Output is correct
13 Correct 1758 ms 3792 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 1 ms 376 KB Output is correct
3 Correct 3 ms 380 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 14 ms 352 KB Output is correct
7 Correct 931 ms 1716 KB Output is correct
8 Correct 1133 ms 1912 KB Output is correct
9 Correct 1687 ms 3704 KB Output is correct
10 Correct 1826 ms 3800 KB Output is correct
11 Correct 1846 ms 3796 KB Output is correct
12 Correct 2932 ms 3832 KB Output is correct
13 Correct 1758 ms 3792 KB Output is correct
14 Correct 1756 ms 2168 KB Output is correct
15 Correct 1790 ms 2540 KB Output is correct
16 Correct 4581 ms 4024 KB Output is correct
17 Correct 6242 ms 5132 KB Output is correct
18 Correct 5875 ms 5240 KB Output is correct
19 Correct 4426 ms 5120 KB Output is correct
20 Correct 5629 ms 5128 KB Output is correct
21 Correct 5512 ms 5124 KB Output is correct
22 Correct 3187 ms 5112 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 1 ms 376 KB Output is correct
3 Correct 3 ms 380 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 376 KB Output is correct
6 Correct 14 ms 352 KB Output is correct
7 Correct 931 ms 1716 KB Output is correct
8 Correct 1133 ms 1912 KB Output is correct
9 Correct 1687 ms 3704 KB Output is correct
10 Correct 1826 ms 3800 KB Output is correct
11 Correct 1846 ms 3796 KB Output is correct
12 Correct 2932 ms 3832 KB Output is correct
13 Correct 1758 ms 3792 KB Output is correct
14 Correct 1756 ms 2168 KB Output is correct
15 Correct 1790 ms 2540 KB Output is correct
16 Correct 4581 ms 4024 KB Output is correct
17 Correct 6242 ms 5132 KB Output is correct
18 Correct 5875 ms 5240 KB Output is correct
19 Correct 4426 ms 5120 KB Output is correct
20 Correct 5629 ms 5128 KB Output is correct
21 Correct 5512 ms 5124 KB Output is correct
22 Correct 3187 ms 5112 KB Output is correct
23 Execution timed out 9088 ms 10424 KB Time limit exceeded
24 Halted 0 ms 0 KB -