Submission #171372

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
171372	2019-12-28T12:01:23 Z	arnold518	Dancing Elephants (IOI11_elephants)	C++14	Compilation error	0 ms	0 KB

elephants

#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;
int SQ = 100;
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+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; SQ2=sqrt(N)+1;

    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:19:17: error: array bound is not an integer constant before ']' token
 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];
                 ^
elephants.cpp:19:28: error: array bound is not an integer constant before ']' token
 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];
                            ^
elephants.cpp:19:43: error: array bound is not an integer constant before ']' token
 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];
                                           ^
elephants.cpp:19:54: error: array bound is not an integer constant before ']' token
 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];
                                                      ^
elephants.cpp:19:69: error: array bound is not an integer constant before ']' token
 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];
                                                                     ^
elephants.cpp:19:80: error: array bound is not an integer constant before ']' token
 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];
                                                                                ^
elephants.cpp:19:96: error: array bound is not an integer constant before ']' token
 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];
                                                                                                ^
elephants.cpp: In function 'void calc(int)':
elephants.cpp:24:10: error: 'P' was not declared in this scope
     sort(P[num], P[num]+sz[num]);
          ^
elephants.cpp:24:25: error: 'sz' was not declared in this scope
     sort(P[num], P[num]+sz[num]);
                         ^~
elephants.cpp:25:31: error: 'Q' was not declared in this scope
     for(i=0; i<=sz[num]; i++) Q[num][i]=R[num][i]=0;
                               ^
elephants.cpp:25:41: error: 'R' was not declared in this scope
     for(i=0; i<=sz[num]; i++) Q[num][i]=R[num][i]=0;
                                         ^
elephants.cpp:29:26: error: 'Q' was not declared in this scope
         if(pos==sz[num]) Q[num][i]=P[num][i]+L, R[num][i]=1;
                          ^
elephants.cpp:29:49: error: 'R' was not declared in this scope
         if(pos==sz[num]) Q[num][i]=P[num][i]+L, R[num][i]=1;
                                                 ^
elephants.cpp:30:14: error: 'Q' was not declared in this scope
         else Q[num][i]=Q[num][pos], R[num][i]=R[num][pos]+1;
              ^
elephants.cpp:30:37: error: 'R' was not declared in this scope
         else Q[num][i]=Q[num][pos], R[num][i]=R[num][pos]+1;
                                     ^
elephants.cpp:23:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
elephants.cpp: In function 'void make()':
elephants.cpp:40:32: error: 'sz' was not declared in this scope
     for(i=0; i<=(N-1)/SQ; i++) sz[i]=0;
                                ^~
elephants.cpp:41:24: error: 'P' was not declared in this scope
     for(i=0; i<N; i++) P[i/SQ][sz[i/SQ]++]=C[i].first, B[C[i].second]=i/SQ;
                        ^
elephants.cpp:41:32: error: 'sz' was not declared in this scope
     for(i=0; i<N; i++) P[i/SQ][sz[i/SQ]++]=C[i].first, B[C[i].second]=i/SQ;
                                ^~
elephants.cpp:37:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
elephants.cpp: In function 'void pop(int)':
elephants.cpp:50:16: error: 'sz' was not declared in this scope
     for(i=0; i<sz[num]; i++) if(P[num][i]==A[p]) break;
                ^~
elephants.cpp:50:33: error: 'P' was not declared in this scope
     for(i=0; i<sz[num]; i++) if(P[num][i]==A[p]) break;
                                 ^
elephants.cpp:52:20: error: 'sz' was not declared in this scope
     for(i=pos+1; i<sz[num]; i++) P[num][i-1]=P[num][i];
                    ^~
elephants.cpp:52:34: error: 'P' was not declared in this scope
     for(i=pos+1; i<sz[num]; i++) P[num][i-1]=P[num][i];
                                  ^
elephants.cpp:53:5: error: 'sz' was not declared in this scope
     sz[num]--;
     ^~
elephants.cpp:47:12: warning: unused variable 'j' [-Wunused-variable]
     int i, j;
            ^
elephants.cpp: In function 'void push(int, int)':
elephants.cpp:65:5: error: 'P' was not declared in this scope
     P[num][sz[num]++]=x;
     ^
elephants.cpp:65:12: error: 'sz' was not declared in this scope
     P[num][sz[num]++]=x;
            ^~
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:87:29: error: 'P' was not declared in this scope
         int pos=upper_bound(P[i], P[i]+sz[i], bef)-P[i];
                             ^
elephants.cpp:87:40: error: 'sz' was not declared in this scope
         int pos=upper_bound(P[i], P[i]+sz[i], bef)-P[i];
                                        ^~
elephants.cpp:89:14: error: 'R' was not declared in this scope
         ans+=R[i][pos];
              ^
elephants.cpp:90:13: error: 'Q' was not declared in this scope
         bef=Q[i][pos];
             ^
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;
            ^