nlogn的multiset为什么TLE#9,求调玄关

sunqihuan @ 2024-12-08 16:32:13

#include<bits/stdc++.h>
using namespace std;
static int n,m,a[1000005];
multiset<int> s,s2;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+ch-'0',ch=getchar();
   return s*w;
}
inline void write(int x){
    if(x<0) {
        putchar('-');
        x = -x;
    }
    if(x>9) write(x / 10);
    putchar(x % 10 + '0');
}
int main(){
    n=read();
    m=read();
    for(register int i=1;i<=n;i++){
        a[i]=read();
        if(i<=m)s.insert(a[i]);
        else {
            write(*s.begin());
            putchar(' ');
            multiset<int> :: iterator it=s.find(a[i-m]);
            s.erase(it);
            s.insert(a[i]);
        }
    }
    write(*s.begin());
    puts("");
    for(register int i=1;i<=n;i++){
        if(i<=m)s2.insert(a[i]);
        else {
            write(*(--s2.end()));
            putchar(' ');
            multiset<int> :: iterator it=s2.find(a[i-m]);
            s2.erase(it);
            s2.insert(a[i]);
        }
    }
    write(*(--s2.end()));
    return 0;
}

by litjohn @ 2024-12-08 17:03:22

@sunqihuan multiset 常数巨大

by sunqihuan @ 2024-12-08 17:07:49

但是也能卡过去啊QWQ可不可以叫我怎样卡

by sunqihuan @ 2024-12-08 17:08:02

@litjohn

by yinbe2 @ 2024-12-08 17:09:02

@sunqihuan等会，我试一下

by sunqihuan @ 2024-12-08 17:10:16

谢谢

by yinbe2 @ 2024-12-08 17:41:42

@sunqihuan

卡过去了

代码：

#include<bits/stdc++.h>
using namespace std;
static int n,m,a[1000005],ans[1000005];
multiset<int> s,s2;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=(s<<3)+(s<<1)+(ch^'0'),ch=getchar();
   return s*w;
}
inline void write(int x){
    if(!x)
    {
        putchar('0');
        return;
    }
    if(x<0)
    {
        x=-x;
        putchar('-');
    }
    int len=0,s[30];
    while(x)
    {
        s[len++]=x%10;
        x/=10;
    }
    while(len--)
        putchar(s[len]^48);
    putchar(' ');   
}
int main(){
//  freopen("p1886.in","r",stdin);
//  freopen("p1886.out","w",stdout);
    n=read();
    m=read();
    for(register int i=1;i<=n;i++){
        a[i]=read();
        if(i<=m)s.insert(a[i]);
        else {
            write(*s.begin());
            ans[i-m]=(*(--s.end()));
            s.erase(s.find(a[i-m]));
            s.insert(a[i]);
        }
    }
    write(*s.begin());
    ans[n-m+1]=(*(--s.end()));
    puts("");
    int i;
    for(i=1;i+7<=n-m+1;i+=8)
    {
        write(ans[i]);
        write(ans[i+1]);
        write(ans[i+2]);
        write(ans[i+3]);
        write(ans[i+4]);
        write(ans[i+5]);
        write(ans[i+6]);
        write(ans[i+7]);
    }
    while(n-m+1-i+1)
    {
        write(ans[i]);
        i++;
    }
    return 0;
}