結果

問題 No.2758 RDQ
ユーザー tails
提出日時 2024-05-17 22:22:27
言語 C90
(gcc 12.3.0)
結果
WA  
実行時間 -
コード長 1,750 bytes
コンパイル時間 1,347 ms
コンパイル使用メモリ 29,168 KB
実行使用メモリ 25,844 KB
最終ジャッジ日時 2024-12-20 14:19:54
合計ジャッジ時間 2,395 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 6 WA * 15
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.c: In function ‘sort’:
main.c:53:15: warning: initialization of ‘int *’ from incompatible pointer type ‘char *’ [-Wincompatible-pointer-types]
   53 |         int*b=wbuf;
      |               ^~~~
main.c: In function ‘main’:
main.c:96:9: warning: implicit declaration of function ‘write’ [-Wimplicit-function-declaration]
   96 |         write(1,wbuf,wp-wbuf);
      |         ^~~~~
main.c:97:9: warning: implicit declaration of function ‘_exit’ [-Wimplicit-function-declaration]
   97 |         _exit(0);
      |         ^~~~~
main.c:97:9: warning: incompatible implicit declaration of built-in function ‘_exit’ [-Wbuiltin-declaration-mismatch]

ソースコード

diff #
プレゼンテーションモードにする

#pragma GCC optimize("Ofast")
#pragma GCC target("avx2")
#define rd_init() char*rp=({char*mmap();mmap(0l,1l<<25,1,2,0,0ll);})
#define rd() ({int _v=0,_c;while(_c=*rp++-48,_c>=0)_v=_v*10+_c;_v;})
#define wt(v) {unsigned _z=v,_n=0;ulong _d=0;while(++_n,_d=_d<<8|0x30|_z%10,_z/=10);*(ulong*)wp=_d;wp+=_n;}
#define rep(v,e) for(typeof(e) v=0;v<e;++v)
#define reps(v,s,e) for(typeof(e) v=s;v<e;++v)
#define repst(v,s,e,t) for(typeof(e) v=s;v<e;v+=t)
typedef unsigned long ulong;
char wbuf[1<<25];
int ds[50001][100],dn[50001];
int a[50000];
struct{int l,r,k;} qs[50000];
int qi[100000];
int z[50000];
int c[100001];
void f0(){
    reps(i,1,50001){
        repst(j,i,50001,i){
            ds[j][dn[j]++]=i;
        }
    }
}
void sort_aux(int*a,int*b,int n,int p){
    int c[256];
    for(int i=0;i<256;++i){
        c[i]=0;
    }
    for(int i=0;i<n;++i){
        int u=a[i];
        unsigned v=u&1?qs[u>>1].r<<1|1:qs[u>>1].l<<1|0;
        ++c[v>>(p<<3)&255];
    }
    int t=0;
    for(int i=0;i<256;++i){
        int u=c[i];
        c[i]=t;
        t+=u;
    }
    for(int i=0;i<n;++i){
        int u=a[i];
        unsigned v=u&1?qs[u>>1].r<<1|1:qs[u>>1].l<<1|0;
        b[c[v>>(p<<3)&255]++]=u;
    }
}
void sort(int*a,int n){
    int*b=wbuf;
    sort_aux(a,b,n,0);
    sort_aux(b,a,n,1);
    sort_aux(a,b,n,2);
    sort_aux(b,a,n,3);
}
int main(){
    f0();
    rd_init();
    int n=rd();
    int q=rd();
    rep(i,n){
        a[i]=rd();
    }
    rep(j,q){
        qs[j].l=rd()-1;
        qs[j].r=rd()-1;
        qs[j].k=rd();
    }
    rep(j,q*2){
        qi[j]=j;
    }
    sort(qi,q*2);
    int d=0;
    rep(i,n){
        while(d<n*2&&!(qi[d]&1)&&qs[qi[d]>>1].l==i){
            z[qi[d]>>1]=-c[qs[qi[d]>>1].k];
            ++d;
        }
        rep(b,dn[a[i]]){
            c[ds[a[i]][b]]+=1;
        }
        while(d<n*2&&(qi[d]&1)&&qs[qi[d]>>1].r==i){
            z[qi[d]>>1]+=c[qs[qi[d]>>1].k];
            ++d;
        }
    }
    char*wp=wbuf;
    rep(j,q){
        wt(z[j]);
        *wp++='\n';
    }
    write(1,wbuf,wp-wbuf);
    _exit(0);
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0