oj.uz

Submission #53865

# Submission time Handle Problem Language Result Execution time Memory
53865 2018-07-01T12:51:43 Z TadijaSebez Secret (JOI14_secret) C++11
0 / 100
 648 ms 5456 KB 
#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(x,a[i]);
        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;
}
*/

Compilation message

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
0.0 / 100.0

# Verdict Execution time Memory Grader output
1 Incorrect 156 ms 2552 KB Wrong Answer: Query(222, 254) - expected : 34031541, actual : 268854015.
2 Incorrect 168 ms 2620 KB Wrong Answer: Query(60, 375) - expected : 669221184, actual : 311474560.
3 Incorrect 159 ms 2764 KB Wrong Answer: Query(211, 401) - expected : 674373968, actual : 353554500.
4 Incorrect 588 ms 4780 KB Wrong Answer: Query(90, 497) - expected : 397934825, actual : 343081568.
5 Incorrect 580 ms 4976 KB Wrong Answer: Query(587, 915) - expected : 752404486, actual : 957013316.
6 Incorrect 593 ms 5120 KB Wrong Answer: Query(738, 741) - expected : 983692994, actual : 850129153.
7 Incorrect 625 ms 5360 KB Wrong Answer: Query(84, 976) - expected : 742463504, actual : 675449873.
8 Incorrect 648 ms 5376 KB Wrong Answer: Query(58, 987) - expected : 20022464, actual : 273091792.
9 Incorrect 607 ms 5376 KB Wrong Answer: Query(33, 967) - expected : 676869696, actual : 827853577.
10 Incorrect 606 ms 5456 KB Wrong Answer: Query(116, 961) - expected : 68487362, actual : 337854787.