oj.uz

답안 #171326

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
171326 2019-12-28T10:59:47 Z arnold518 코끼리 (Dancing Elephants) (IOI11_elephants) C++14
97 / 100
 9000 ms 10364 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 = 400;

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 380 KB Output is correct
3 Correct 2 ms 380 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 380 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 2 ms 452 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 380 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 2 ms 452 KB Output is correct
7 Correct 1606 ms 1704 KB Output is correct
8 Correct 1686 ms 1984 KB Output is correct
9 Correct 1821 ms 3768 KB Output is correct
10 Correct 1937 ms 3776 KB Output is correct
11 Correct 1780 ms 3704 KB Output is correct
12 Correct 3316 ms 3780 KB Output is correct
13 Correct 1811 ms 3704 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 380 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 2 ms 452 KB Output is correct
7 Correct 1606 ms 1704 KB Output is correct
8 Correct 1686 ms 1984 KB Output is correct
9 Correct 1821 ms 3768 KB Output is correct
10 Correct 1937 ms 3776 KB Output is correct
11 Correct 1780 ms 3704 KB Output is correct
12 Correct 3316 ms 3780 KB Output is correct
13 Correct 1811 ms 3704 KB Output is correct
14 Correct 2414 ms 2256 KB Output is correct
15 Correct 2793 ms 2656 KB Output is correct
16 Correct 4896 ms 4088 KB Output is correct
17 Correct 5666 ms 5116 KB Output is correct
18 Correct 5684 ms 5136 KB Output is correct
19 Correct 6216 ms 5112 KB Output is correct
20 Correct 5546 ms 5124 KB Output is correct
21 Correct 5405 ms 5240 KB Output is correct
22 Correct 2313 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 380 KB Output is correct
3 Correct 2 ms 380 KB Output is correct
4 Correct 3 ms 376 KB Output is correct
5 Correct 3 ms 504 KB Output is correct
6 Correct 2 ms 452 KB Output is correct
7 Correct 1606 ms 1704 KB Output is correct
8 Correct 1686 ms 1984 KB Output is correct
9 Correct 1821 ms 3768 KB Output is correct
10 Correct 1937 ms 3776 KB Output is correct
11 Correct 1780 ms 3704 KB Output is correct
12 Correct 3316 ms 3780 KB Output is correct
13 Correct 1811 ms 3704 KB Output is correct
14 Correct 2414 ms 2256 KB Output is correct
15 Correct 2793 ms 2656 KB Output is correct
16 Correct 4896 ms 4088 KB Output is correct
17 Correct 5666 ms 5116 KB Output is correct
18 Correct 5684 ms 5136 KB Output is correct
19 Correct 6216 ms 5112 KB Output is correct
20 Correct 5546 ms 5124 KB Output is correct
21 Correct 5405 ms 5240 KB Output is correct
22 Correct 2313 ms 5112 KB Output is correct
23 Execution timed out 9009 ms 10364 KB Time limit exceeded
24 Halted 0 ms 0 KB -