oj.uz

Submission #53866

# Submission time Handle Problem Language Result Execution time Memory
53866 2018-07-01T12:55:08 Z TadijaSebez Secret (JOI14_secret) C++11
100 / 100
 696 ms 4812 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(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;
}
*/

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

# Verdict Execution time Memory Grader output
1 Correct 188 ms 2552 KB Output is correct - number of calls to Secret by Init = 3331, maximum number of calls to Secret by Query = 1
2 Correct 215 ms 2664 KB Output is correct - number of calls to Secret by Init = 3339, maximum number of calls to Secret by Query = 1
3 Correct 211 ms 2664 KB Output is correct - number of calls to Secret by Init = 3347, maximum number of calls to Secret by Query = 1
4 Correct 634 ms 4548 KB Output is correct - number of calls to Secret by Init = 7467, maximum number of calls to Secret by Query = 1
5 Correct 679 ms 4812 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
6 Correct 598 ms 4812 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
7 Correct 658 ms 4812 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
8 Correct 696 ms 4812 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
9 Correct 604 ms 4812 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1
10 Correct 593 ms 4812 KB Output is correct - number of calls to Secret by Init = 7476, maximum number of calls to Secret by Query = 1