Codeforces 380 A. Sereja and Prefixes

2023-11-10 13:55:22

用longlong才能A。。。。。。害我TLE了半天。。。。

用一个结构体记录，操作改变的区间范围 [ c1 , c2 ] , v ,youxiao

注意c1==c2时，并不一定表示一个有效的值所以需要一个标记。。。。

当这个区间表示一个有效的值时，v表示有效值。。。。。否则v表示重复了多少次（用来递推）

Sereja loves number sequences very much. That‘s why he decided to make himself a new one following a certain algorithm.

Sereja takes a blank piece of paper. Then he starts writing out the sequence in m stages. Each time he either adds a new number to the end of the sequence or takes l first elements of the current sequence and adds them c times to the end. More formally, if we represent the current sequence as a1,?a2,?...,?an, then after we apply the described operation, the sequence transforms intoa1,?a2,?...,?an[,?a1,?a2,?...,?al] (the block in the square brackets must be repeated c times).

A day has passed and Sereja has completed the sequence. He wonders what are the values of some of its elements. Help Sereja.

Input

The first line contains integer m (1?≤?m?≤?105) — the number of stages to build a sequence.

Next m lines contain the description of the stages in the order they follow. The first number in the line is a type of stage (1 or 2). Type 1 means adding one number to the end of the sequence, in this case the line contains integer xi (1?≤?xi?≤?105) — the number to add. Type 2 means copying a prefix of length li to the end ci times, in this case the line further contains two integers li,?ci (1?≤?li?≤?105,?1?≤?ci?≤?104), li is the length of the prefix, ci is the number of copyings. It is guaranteed that the length of prefix li is never larger than the current length of the sequence.

The next line contains integer n (1?≤?n?≤?105) — the number of elements Sereja is interested in. The next line contains the numbers of elements of the final sequence Sereja is interested in. The numbers are given in the strictly increasing order. It is guaranteed that all numbers are strictly larger than zero and do not exceed the length of the resulting sequence. Consider the elements of the final sequence numbered starting from 1 from the beginning to the end of the sequence.

Please, do not use the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64dspecifier.

Output

Print the elements that Sereja is interested in, in the order in which their numbers occur in the input.

Sample test(s)

input
6
1 1
1 2
2 2 1
1 3
2 5 2
1 4
16
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

output
1 2 1 2 3 1 2 1 2 3 1 2 1 2 3 4

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

const long long int maxn5=1010000;

struct Interval
{
    long long int c1,c2,v,youxiao;
}I[maxn5];

long long int n,m,ct,high;

long long int getINT(long long int x)
{
    long long int low=0,high=ct-1,mid,ans;
    while(low<=high)
    {
        mid=(low+high)>>1;
        if((x>I[mid].c1&&x<I[mid].c2)||x==I[mid].c1||x==I[mid].c2)
        {
            ans=mid; break;
        }
        else if(x>I[mid].c2)
        {
            low=mid+1;
        }
        else if(x<I[mid].c1)
        {
            high=mid-1;
        }
    }
    return ans;
}

int main()
{
    scanf("%I64d",&m);
    while(m--)
    {
        long long int a,b,c;
        scanf("%I64d",&a);
        if(a==1)
        {
            scanf("%I64d",&b);
            I[ct++]=(Interval){high,high,b,1};
            high++;
        }
        else if(a==2)
        {
            scanf("%I64d%I64d",&b,&c);
            I[ct++]=(Interval){high,high+c*b-1,c,0};
            high=high+c*b;
        }
    }
    scanf("%I64d",&n);
    while(n--)
    {
        long long int x,ans;
        scanf("%I64d",&x);
        x--;
        ///>_<
        bool flag=true;
        while(flag)
        {
            long long int qj=getINT(x);
            if(I[qj].youxiao)
            {
                ans=I[qj].v;
                flag=false;
                break;
            }
            else if(!I[qj].youxiao)
            {
                int len=x-I[qj].c1;
                int jie=(I[qj].c2-I[qj].c1+1)/I[qj].v;
                x=len%jie;
            }
        }
        printf("%I64d ",ans);
    }
    putchar(10);
    return 0;
}

Codeforces 380 A. Sereja and Prefixes

码农公寓

相关文章