제출 #53866

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
53866		TadijaSebez	비밀 (JOI14_secret)	C++11	100 / 100	696 ms	4812 KiB

secret

#include "secret.h"
#include <stdio.h>
#include <vector>
#include <algorithm>
using namespace std;
const int N=1050;
int a[N],n,val[N][10];
int dep[N];
//---------------------//
//int Secret(int a, int b){ return a+b;}
//---------------------//
void Build(int l, int r, int d)
{
    int i;
    if(r-l<0) return;
    int mid=l+r>>1;
    dep[mid]=d;
    int x=a[mid];
    for(i=mid;i>=l;i--)
    {
        if(i!=mid) x=Secret(a[i],x);
        val[i][d]=x;
    }
    x=a[mid+1];
    for(i=mid+1;i<=r;i++)
    {
        if(i!=mid+1) x=Secret(x,a[i]);
        val[i][d]=x;
    }
    Build(l,mid-1,d+1);
    Build(mid+1,r,d+1);
}
int rmq[N][12],logs[N];
void Init(int N, int A[])
{
    n=N;int i,j;
    for(i=1;i<=n;i++) a[i]=A[i-1],dep[i]=N;
    Build(1,n,0);
    for(i=1;i<=n;i++) rmq[i][0]=i;
    for(j=1;j<12;j++)
    {
        for(i=1;i<=n-(1<<j)+1;i++)
        {
            if(dep[rmq[i][j-1]]<dep[rmq[i+(1<<j-1)][j-1]])
                rmq[i][j]=rmq[i][j-1];
            else rmq[i][j]=rmq[i+(1<<j-1)][j-1];
        }
    }
    for(i=2;i<=n;i++) logs[i]=logs[i>>1]+1;
    //for(i=1;i<=n;i++) printf("%i ",dep[i]);printf("\n");
}
int RMQ(int l, int r)
{
    int k=logs[r-l+1];
    if(dep[rmq[l][k]]<dep[rmq[r-(1<<k)+1][k]]) return rmq[l][k];
    else return rmq[r-(1<<k)+1][k];
}
int Query(int l, int r)
{
    l++;r++;
    //if(l==r) return a[l];
    //if(l+1==r) return Secret(a[l],a[r]);
    int cen=RMQ(l,r);
    if(cen==r) return val[l][dep[cen]];
    return Secret(val[l][dep[cen]],val[r][dep[cen]]);
}
int A[N];
/*
int main()
{
    int N,q,l,r,i;
    scanf("%i",&N);
    for(i=0;i<N;i++) scanf("%i",&A[i]);
    Init(N,A);
    scanf("%i",&q);
    while(q--) scanf("%i %i",&l,&r),printf("%i\n",Query(l,r));
    return 0;
}
*/

컴파일 시 표준 에러 (stderr) 메시지

secret.cpp: In function 'void Build(int, int, int)':
secret.cpp:16:14: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
     int mid=l+r>>1;
             ~^~
secret.cpp: In function 'void Init(int, int*)':
secret.cpp:44:48: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
             if(dep[rmq[i][j-1]]<dep[rmq[i+(1<<j-1)][j-1]])
                                               ~^~
secret.cpp:46:39: warning: suggest parentheses around '-' inside '<<' [-Wparentheses]
             else rmq[i][j]=rmq[i+(1<<j-1)][j-1];
                                      ~^~

• Subtask 1: 100 / 100