2018 UESTC Training for Data Structures美味しいけど餃子

2497 ワード

データ構造

ギョーザにはかなわない
単調キュー保守区間最値(コード粗さ)

//27MS   3200KB
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int MAX=1e5+5;
pairA[MAX];
pairQ[MAX];
int T,L;
void read(int &x)
{
    int f=1;x=0;char c=getchar();
    while (c>'9'||c='0'){x=x*10+c-'0';c=getchar();}
    x*=f;
}
int main()
{
    int n,m,x,y,len;
    string a,b;
    read(n);read(m);
    for (int k=1;k<=n;k++)
    {
        read(x);read(y);
        A[k].first=x;
        A[k].second=y;
    }
    sort(A+1,A+n+1);
    for (int k=1;k<=m;k++)
    {
        cin>>a>>b;
        read(len);
        T=0;L=-1;
        int ans=0,sum=0;
        memset(Q,0,sizeof(Q));
        if (a=="gt")
        {
            if (b=="min")
            {
                for (int i=1;i<=n;i++)
                {
                    while (A[i].first-Q[T].first>len&&L>=T) T++;
                    if (LQ[T].second) ans++;
                    while (Q[L].second>A[i].second&&L>=T) L--;
                    Q[++L].first=A[i].first;
                    Q[L].second=A[i].second;
                }
            }
            else if (b=="max")
            {
                for (int i=1;i<=n;i++)
                {
                    while (A[i].first-Q[T].first>len&&L>=T) T++;
                    if (LQ[T].second) ans++;
                    while (Q[L].second=T) L--;
Q[++L].first=A[i].first;
Q[L].second=A[i].second;
}
}
else
{
for (int i=1;i<=n;i++)
{
while (A[i].first-Q[T].first>len&&L>=T) {sum-=Q[T].second;T++;}
if (L=(sum/(L-T+1)+1)) ans++;
Q[++L].first=A[i].first;
Q[L].second=A[i].second;
sum+=A[i].second;
}
}
}
else
{
if (b=="min")
{
for (int i=1;i<=n;i++)
{
while (A[i].first-Q[T].first>len&&L>=T) T++;
if (LA[i].second&&L>=T) L--;
Q[++L].first=A[i].first;
Q[L].second=A[i].second;
}
}
else if (b=="max")
{
for (int i=1;i<=n;i++)
{
while (A[i].first-Q[T].first>len&&L>=T) T++;
if (L=T) L--;
Q[++L].first=A[i].first;
Q[L].second=A[i].second;
}
}
else
{
for (int i=1;i<=n;i++)
{
while (A[i].first-Q[T].first>len&&L>=T) {sum-=Q[T].second;T++;}
if (L

send-mail: fatal: user1(1000): queue file write error とは、サイズ制限に引っかかったということ。

マルチスレッドyieldはcpuを譲ってスレッドにノートを勉強させます