だから私は再び助けが必要です.私は最近codechefで中レベルの問題を始めたので、TLEをかなり多く受けています.
したがって、基本的に問題は、質問で指定された複数の最大範囲クエリの合計を見つけることです。最初の範囲が指定され、問題で指定された式によって次の値が計算されます。
この問題を解決するためにセグメント ツリーを使用しましたが、いくつかのサブタスクで TLE を取得し続けています。このコードの最適化を手伝ってください。
問題のリンク - https://www.codechef.com/problems/FRMQ
//solved using segment tree
#include <stdio.h>
#define gc getchar_unlocked
inline int read_int() //fast input function
{
char c = gc();
while(c<'0' || c>'9')
c = gc();
int ret = 0;
while(c>='0' && c<='9')
{
ret = 10 * ret + c - '0';
c = gc();
}
return ret;
}
int min(int a,int b)
{
return (a<b?a:b);
}
int max(int a,int b)
{
return (a>b?a:b);
}
void construct(int a[],int tree[],int low,int high,int pos) //constructs
{ //the segment tree by recursion
if(low==high)
{
tree[pos]=a[low];
return;
}
int mid=(low+high)>>1;
construct(a,tree,low,mid,(pos<<1)+1);
construct(a,tree,mid+1,high,(pos<<1)+2);
tree[pos]=max(tree[(pos<<1)+1],tree[(pos<<1)+2]);
}
int query(int tree[],int qlow,int qhigh,int low,int high,int pos)
{ //function finds the maximum value using the 3 cases
if(qlow<=low && qhigh>=high)
return tree[pos]; //total overlap
if(qlow>high || qhigh<low)
return -1; //no overlap
int mid=(low+high)>>1; //else partial overlap
return max(query(tree,qlow,qhigh,low,mid,(pos<<1)+1),query(tree,qlow,qhigh,mid+1,high,(pos<<1)+2));
}
int main()
{
int n,m,i,temp,x,y,ql,qh;
long long int sum;
n=read_int();
int a[n];
for(i=0;i<n;i++)
a[i]=read_int();
i=1;
while(temp<n) //find size of tree
{
temp=1<<i;
i++;
}
int size=(temp<<1)-1;
int tree[size];
construct(a,tree,0,n-1,0);
m=read_int();
x=read_int();
y=read_int();
sum=0;
for(i=0;i<m;i++)
{
ql=min(x,y);
qh=max(x,y);
sum+=query(tree,ql,qh,0,n-1,0);
x=(x+7)%(n-1); //formula to generate the range of query
y=(y+11)%n;
}
printf("%lld",sum);
return 0;
}