oj.uz

답안 #171324

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
171324 2019-12-28T10:57:28 Z arnold518 코끼리 (Dancing Elephants) (IOI11_elephants) C++14
97 / 100
 9000 ms 10532 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 = 330;
const int SQ2 = 250;

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:20:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
elephants.cpp: In function 'void make()':
elephants.cpp:34:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
elephants.cpp: In function 'void pop(int)':
elephants.cpp:44:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
elephants.cpp: In function 'void push(int, int)':
elephants.cpp:58:9: warning: unused variable 'i' [-Wunused-variable]
     int i, j;
         ^
elephants.cpp:58:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
elephants.cpp: In function 'void init(int, int, int*)':
elephants.cpp:70:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
elephants.cpp: In function 'int query()':
elephants.cpp:79:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
elephants.cpp: In function 'int update(int, int)':
elephants.cpp:96:9: warning: unused variable 'i' [-Wunused-variable]
     int i, j;
         ^
elephants.cpp:96:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^

Subtask #1
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 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

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 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 3 ms 348 KB Output is correct
6 Correct 2 ms 376 KB Output is correct

Subtask #3
24.0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 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 3 ms 348 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 1672 ms 1696 KB Output is correct
8 Correct 1777 ms 1996 KB Output is correct
9 Correct 2040 ms 3764 KB Output is correct
10 Correct 1921 ms 3776 KB Output is correct
11 Correct 1839 ms 3832 KB Output is correct
12 Correct 3812 ms 3768 KB Output is correct
13 Correct 1783 ms 3772 KB Output is correct

Subtask #4
47.0 / 47.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 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 3 ms 348 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 1672 ms 1696 KB Output is correct
8 Correct 1777 ms 1996 KB Output is correct
9 Correct 2040 ms 3764 KB Output is correct
10 Correct 1921 ms 3776 KB Output is correct
11 Correct 1839 ms 3832 KB Output is correct
12 Correct 3812 ms 3768 KB Output is correct
13 Correct 1783 ms 3772 KB Output is correct
14 Correct 2539 ms 2216 KB Output is correct
15 Correct 3014 ms 2532 KB Output is correct
16 Correct 5629 ms 4008 KB Output is correct
17 Correct 6633 ms 5116 KB Output is correct
18 Correct 6635 ms 5112 KB Output is correct
19 Correct 6298 ms 5120 KB Output is correct
20 Correct 6890 ms 5112 KB Output is correct
21 Correct 6654 ms 5116 KB Output is correct
22 Correct 2635 ms 5112 KB Output is correct

Subtask #5
0 / 3.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 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 3 ms 348 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 1672 ms 1696 KB Output is correct
8 Correct 1777 ms 1996 KB Output is correct
9 Correct 2040 ms 3764 KB Output is correct
10 Correct 1921 ms 3776 KB Output is correct
11 Correct 1839 ms 3832 KB Output is correct
12 Correct 3812 ms 3768 KB Output is correct
13 Correct 1783 ms 3772 KB Output is correct
14 Correct 2539 ms 2216 KB Output is correct
15 Correct 3014 ms 2532 KB Output is correct
16 Correct 5629 ms 4008 KB Output is correct
17 Correct 6633 ms 5116 KB Output is correct
18 Correct 6635 ms 5112 KB Output is correct
19 Correct 6298 ms 5120 KB Output is correct
20 Correct 6890 ms 5112 KB Output is correct
21 Correct 6654 ms 5116 KB Output is correct
22 Correct 2635 ms 5112 KB Output is correct
23 Execution timed out 9077 ms 10532 KB Time limit exceeded
24 Halted 0 ms 0 KB -