oj.uz

Submission #171348

# Submission time Handle Problem Language Result Execution time Memory
171348 2019-12-28T11:21:57 Z arnold518 Dancing Elephants (IOI11_elephants) C++14
97 / 100
 9000 ms 10376 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 = 150;
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*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==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 376 KB Output is correct
2 Correct 1 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 376 KB Output is correct
2 Correct 1 ms 376 KB Output is correct
3 Correct 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 248 KB Output is correct
6 Correct 3 ms 376 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 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 248 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 652 ms 1804 KB Output is correct
8 Correct 801 ms 1912 KB Output is correct
9 Correct 1102 ms 3832 KB Output is correct
10 Correct 1315 ms 3804 KB Output is correct
11 Correct 1417 ms 3832 KB Output is correct
12 Correct 2130 ms 3832 KB Output is correct
13 Correct 1291 ms 3960 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 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 248 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 652 ms 1804 KB Output is correct
8 Correct 801 ms 1912 KB Output is correct
9 Correct 1102 ms 3832 KB Output is correct
10 Correct 1315 ms 3804 KB Output is correct
11 Correct 1417 ms 3832 KB Output is correct
12 Correct 2130 ms 3832 KB Output is correct
13 Correct 1291 ms 3960 KB Output is correct
14 Correct 1181 ms 2268 KB Output is correct
15 Correct 1300 ms 2456 KB Output is correct
16 Correct 3200 ms 4064 KB Output is correct
17 Correct 4182 ms 5240 KB Output is correct
18 Correct 4057 ms 5140 KB Output is correct
19 Correct 3772 ms 5148 KB Output is correct
20 Correct 4195 ms 5216 KB Output is correct
21 Correct 3991 ms 5144 KB Output is correct
22 Correct 2554 ms 5368 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 2 ms 376 KB Output is correct
4 Correct 2 ms 376 KB Output is correct
5 Correct 3 ms 248 KB Output is correct
6 Correct 3 ms 376 KB Output is correct
7 Correct 652 ms 1804 KB Output is correct
8 Correct 801 ms 1912 KB Output is correct
9 Correct 1102 ms 3832 KB Output is correct
10 Correct 1315 ms 3804 KB Output is correct
11 Correct 1417 ms 3832 KB Output is correct
12 Correct 2130 ms 3832 KB Output is correct
13 Correct 1291 ms 3960 KB Output is correct
14 Correct 1181 ms 2268 KB Output is correct
15 Correct 1300 ms 2456 KB Output is correct
16 Correct 3200 ms 4064 KB Output is correct
17 Correct 4182 ms 5240 KB Output is correct
18 Correct 4057 ms 5140 KB Output is correct
19 Correct 3772 ms 5148 KB Output is correct
20 Correct 4195 ms 5216 KB Output is correct
21 Correct 3991 ms 5144 KB Output is correct
22 Correct 2554 ms 5368 KB Output is correct
23 Execution timed out 9055 ms 10376 KB Time limit exceeded
24 Halted 0 ms 0 KB -