結果
問題 | No.2743 Twisted Lattice |
ユーザー |
![]() |
提出日時 | 2024-04-21 11:14:39 |
言語 | C90 (gcc 12.3.0) |
結果 |
AC
|
実行時間 | 18 ms / 3,000 ms |
コード長 | 2,325 bytes |
コンパイル時間 | 173 ms |
コンパイル使用メモリ | 28,288 KB |
実行使用メモリ | 10,112 KB |
最終ジャッジ日時 | 2024-10-13 09:53:57 |
合計ジャッジ時間 | 1,606 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 8 |
コンパイルメッセージ
main.c: In function ‘f3’: main.c:122:9: warning: implicit declaration of function ‘write’ [-Wimplicit-function-declaration] 122 | write(1,wbuf,wp-wbuf); | ^~~~~ main.c: In function ‘main’: main.c:129:9: warning: implicit declaration of function ‘_exit’ [-Wimplicit-function-declaration] 129 | _exit(0); | ^~~~~ main.c:129:9: warning: incompatible implicit declaration of built-in function ‘_exit’ [-Wbuiltin-declaration-mismatch]
ソースコード
#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_skip() while(*rp++>=48)#define rd() ({int _v=0,_c;while(_c=*rp++-48,_c>=0)_v=_v*10+_c;_v;})#define WTHI(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 WTLO(v) {unsigned _z=v,_n=8;ulong _d=0;while(_d=_d<<8|0x30|_z%10,_z/=10,--_n);*(ulong*)wp=_d;wp+=8;}#define wt(v) if(v>=100000000){WTHI(v/100000000);WTLO(v);}else{WTHI(v);}#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 rrep(v,e) for(typeof(e) v=e;v--;)#define max(a,b) (a>=b?a:b)#define chmin(v,a) (v=v<=a?v:a)typedef unsigned long ulong;char wbuf[1<<25];int n;struct{unsigned a,b;}ab[200000];int c[200000];unsigned z[200000];void sort_aux(ulong*a,ulong*b,unsigned*c,unsigned*d){int e[256];for(int i=0;i<256;++i){e[i]=0;}for(int i=0;i<n;++i){++e[a[i]&255];}int t=0;for(int i=0;i<256;++i){int u=e[i];e[i]=t;t+=u;}for(int i=0;i<n;++i){int k=e[a[i]&255]++;b[k]=a[i]>>8|a[i]<<56;d[k]=c[i];}}void sort(){ulong*a=(ulong*)ab;ulong*b=(ulong*)wbuf;unsigned*d=z;sort_aux(a,b,c,d);sort_aux(b,a,d,c);sort_aux(a,b,c,d);sort_aux(b,a,d,c);sort_aux(a,b,c,d);sort_aux(b,a,d,c);sort_aux(a,b,c,d);sort_aux(b,a,d,c);}void f1(){rd_init();rd_skip();rd_skip();n=rd();rep(i,n){ab[i].a=rd();ab[i].b=rd();c[i]=i;}sort();}void f2(){int pa=ab[0].a;int pb=ab[0].b;int q=pa-pb;z[c[0]]=~0;reps(i,1,n){unsigned y;if(ab[i].b==ab[i-1].b){y=ab[i].a-ab[i-1].a;}else{y=q+ab[i].a+ab[i].b-2;if(ab[i].b==pb+1){unsigned x=max(ab[i].a,pa);chmin(y,x);}pa=ab[i].a;pb=ab[i].b;}z[c[i]]=y;chmin(q,(int)(ab[i].a-ab[i].b));}pa=ab[n-1].a;pb=ab[n-1].b;q=pa+pb;rrep(i,n-1){unsigned y=z[c[i]];if(ab[i].b==ab[i+1].b){chmin(y,ab[i+1].a-ab[i].a);}else{pa=ab[i+1].a;pb=ab[i+1].b;}if(ab[i].b==pb-1){unsigned x=max(ab[i].a,pa);chmin(y,x);}chmin(y,q+ab[i].a-ab[i].b-2);z[c[i]]=y;chmin(q,ab[i].a+ab[i].b);}}void f3(){char*wp=wbuf;rep(i,n){wt(z[i]);*wp++='\n';}write(1,wbuf,wp-wbuf);}int main(){f1();f2();f3();_exit(0);}