oj.uz

Submission #171352

# Submission time Handle Problem Language Result Execution time Memory
171352 2019-12-28T11:30:04 Z arnold518 Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 12016 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 = 285;

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;
            ^

Subtask #1
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 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 380 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 6 ms 376 KB Output is correct
6 Correct 7 ms 376 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 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 6 ms 376 KB Output is correct
6 Correct 7 ms 376 KB Output is correct
7 Correct 475 ms 1884 KB Output is correct
8 Correct 547 ms 2296 KB Output is correct
9 Correct 961 ms 4444 KB Output is correct
10 Correct 1446 ms 4352 KB Output is correct
11 Correct 1531 ms 4344 KB Output is correct
12 Correct 1827 ms 4336 KB Output is correct
13 Correct 1468 ms 4472 KB Output is correct

Subtask #4
47.0 / 47.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 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 6 ms 376 KB Output is correct
6 Correct 7 ms 376 KB Output is correct
7 Correct 475 ms 1884 KB Output is correct
8 Correct 547 ms 2296 KB Output is correct
9 Correct 961 ms 4444 KB Output is correct
10 Correct 1446 ms 4352 KB Output is correct
11 Correct 1531 ms 4344 KB Output is correct
12 Correct 1827 ms 4336 KB Output is correct
13 Correct 1468 ms 4472 KB Output is correct
14 Correct 967 ms 2540 KB Output is correct
15 Correct 1016 ms 2808 KB Output is correct
16 Correct 2835 ms 4588 KB Output is correct
17 Correct 3744 ms 5880 KB Output is correct
18 Correct 3756 ms 5888 KB Output is correct
19 Correct 3492 ms 5908 KB Output is correct
20 Correct 3572 ms 6004 KB Output is correct
21 Correct 3612 ms 5880 KB Output is correct
22 Correct 2638 ms 5876 KB Output is correct

Subtask #5
0 / 3.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 380 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 6 ms 376 KB Output is correct
6 Correct 7 ms 376 KB Output is correct
7 Correct 475 ms 1884 KB Output is correct
8 Correct 547 ms 2296 KB Output is correct
9 Correct 961 ms 4444 KB Output is correct
10 Correct 1446 ms 4352 KB Output is correct
11 Correct 1531 ms 4344 KB Output is correct
12 Correct 1827 ms 4336 KB Output is correct
13 Correct 1468 ms 4472 KB Output is correct
14 Correct 967 ms 2540 KB Output is correct
15 Correct 1016 ms 2808 KB Output is correct
16 Correct 2835 ms 4588 KB Output is correct
17 Correct 3744 ms 5880 KB Output is correct
18 Correct 3756 ms 5888 KB Output is correct
19 Correct 3492 ms 5908 KB Output is correct
20 Correct 3572 ms 6004 KB Output is correct
21 Correct 3612 ms 5880 KB Output is correct
22 Correct 2638 ms 5876 KB Output is correct
23 Execution timed out 9003 ms 12016 KB Time limit exceeded
24 Halted 0 ms 0 KB -