QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#399078 | #8546. Min or Max 2 | 275307894a | TL | 4362ms | 50388kb | C++14 | 4.7kb | 2024-04-25 21:38:16 | 2024-04-25 21:38:17 |
Judging History
answer
#include<bits/stdc++.h>
#define Gc() getchar()
#define Me(x,y) memset(x,y,sizeof(x))
#define Mc(x,y) memcpy(x,y,sizeof(x))
#define d(x,y) ((m)*(x-1)+(y))
#define R(n) (rnd()%(n)+1)
#define Pc(x) putchar(x)
#define LB lower_bound
#define UB upper_bound
#define fi first
#define se second
#define eb emplace_back
#define all(x) x.begin(),x.end()
using namespace std;using ll=long long;using db=double;using lb=long db;using ui=unsigned;using ull=unsigned long long;using pii=pair<int,int>;
const int N=5e5+5,M=N*4+5,K=1000+5,mod=998244353,Mod=mod-1;const db eps=1e-8;const int INF=1e9+7;mt19937 rnd(263082);
#define Tp template<typename T>
#define Ts template<typename T,typename... Ar>
namespace Debug{
Tp void _debug(char* f,T t){cerr<<f<<'='<<t<<endl;}
Ts void _debug(char* f,T x,Ar... y){while(*f!=',') cerr<<*f++;cerr<<'='<<x<<",";_debug(f+1,y...);}
#ifdef LOCAL
#define gdb(...) _debug((char*)#__VA_ARGS__,__VA_ARGS__)
#else
#define gdb(...) void()
#endif
}using namespace Debug;
int n,A[N],B[N],ans[N],pl[N];map<pii,int> f;
struct node{
int a,b;
node operator +(const node &B)const{
if(B.b==-1) return B;
if(b==-1) return (node){min(max(B.a,a),B.b),-1};
if(b<B.a) return (node){B.a,-1};
if(a>B.b) return (node){B.b,-1};
return (node){max(a,B.a),min(b,B.b)};
}
int calc(int x){
return ~b?min(max(a,x),b):a;
}
}C[N],l[N],r[N];
namespace SgT{
#define ls v<<1
#define rs v<<1|1
node f[M];
void up(int v){f[v]=f[ls]+f[rs];}
void modify(int x,node y,int l=1,int r=n,int v=1){
if(l==r){f[v]=y;return;}int m=l+r>>1;
x<=m?modify(x,y,l,m,ls):modify(x,y,m+1,r,rs);up(v);
}
node qry(int x,int y,int l=1,int r=n,int v=1){
if(x<=l&&r<=y) return f[v];int m=l+r>>1;
if(y<=m) return qry(x,y,l,m,ls);if(x>m) return qry(x,y,m+1,r,rs);
return qry(x,y,l,m,ls)+qry(x,y,m+1,r,rs);
}
#undef ls
#undef rs
}
struct Tree{
#define ls v<<1
#define rs v<<1|1
int f[M];node g[M];
void up(int v){f[v]=min(f[ls],f[rs]);}
void Pg(int v,node w){
if(f[v]==INF) return;
g[v]=g[v]+w;f[v]=w.calc(f[v]);
}
void P(int v){
if(g[v].a^-INF||g[v].b^INF) Pg(ls,g[v]),Pg(rs,g[v]),g[v]=(node){-INF,INF};
}
void modify(int x,node y,int l=1,int r=n,int v=1){
if(l==r){f[v]=y.calc(f[v]);return;}int m=l+r>>1;P(v);
x<=m?modify(x,y,l,m,ls):modify(x,y,m+1,r,rs);up(v);
}
void add(int x,int y,node z,int l=1,int r=n,int v=1){
if(x>y) return;
if(x<=l&&r<=y) return Pg(v,z);int m=l+r>>1;P(v);
x<=m&&(add(x,y,z,l,m,ls),0);y>m&&(add(x,y,z,m+1,r,rs),0);up(v);
}
int qry(int x,int y,int l=1,int r=n,int v=1){
if(x>y) return INF;
if(x<=l&&r<=y) return f[v];int m=l+r>>1;P(v);
return min(x<=m?qry(x,y,l,m,ls):INF,y>m?qry(x,y,m+1,r,rs):INF);
}
void build(int l=1,int r=n,int v=1){
f[v]=INF;g[v]=(node){-INF,INF};if(l==r) return;
int m=l+r>>1;build(l,m,ls);build(m+1,r,rs);
}
#undef ls
#undef rs
}f1,f2;
void work(node x,int A,int l,int r){
int mi=f1.qry(l,r),mx=n-f2.qry(l,r);//gdb(mi,mx);
if(x.b==-1){
if(mi^INF) f[make_pair(A,x.a)]=1;
}else{
if(mi<=x.a) f[make_pair(A,x.a)]=1;
if(mx>=x.b) f[make_pair(A,x.b)]=1;
}
}
void calc(int *A,int *B){
int i,j;for(i=1;i<=n;i++) pl[A[i]]=i;
for(i=1;i<=n;i++) SgT::modify(i,(node){-INF,B[i]});
for(i=1;i<=n;i++){
int id=pl[i];
l[id]=SgT::qry(id,n);
SgT::modify(id,(node){B[id],INF});
r[id]=SgT::qry(id,n);
}
if(l[1].b==-1) f[make_pair(A[1],l[1].a)]=1;
else f[make_pair(A[1],l[1].b)]=1;
f1.build();f2.build();
f1.modify(A[1],(node){-INF,B[1]});f2.modify(A[1],(node){-INF,n-B[1]});
for(i=2;i<=n;i++){
work(l[i],A[i],A[i],n);work(r[i],A[i],1,A[i]);
int mi=f1.qry(A[i]+1,n),mx=n-f2.qry(A[i]+1,n);
if(mi^INF){
mi=min(mi,B[i]);mx=min(mx,B[i]);
f1.modify(A[i],(node){-INF,mi});f2.modify(A[i],(node){-INF,n-mx});
}
mi=f1.qry(1,A[i]-1),mx=n-f2.qry(1,A[i]-1);
if(mi^INF){
mi=max(mi,B[i]);mx=max(mx,B[i]);
f1.modify(A[i],(node){-INF,mi});f2.modify(A[i],(node){INF,n-mx});
}
f1.add(1,A[i]-1,(node){-INF,B[i]});f2.add(1,A[i]-1,(node){n-B[i],INF});
f1.add(A[i]+1,n,(node){B[i],INF});f2.add(A[i]+1,n,(node){-INF,n-B[i]});
// for(int j=1;j<A[i];j++)if(f1[j]^INF) f1[j]=min(f1[j],B[i]),f2[j]=min(f2[j],B[i]);
// for(int j=A[i]+1;j<=n;j++) if(f1[j]^INF) f1[j]=max(f1[j],B[i]),f2[j]=max(f2[j],B[i]);
}
}
void Solve(){
int i,j;scanf("%d",&n);f.clear();
for(i=1;i<=n;i++) scanf("%d",&A[i]);
for(i=1;i<=n;i++) scanf("%d",&B[i]);
calc(A,B);
map<pii,int> g;swap(g,f);for(auto i:g) f[make_pair(i.fi.se,i.fi.fi)]=1;
calc(B,A);
fill(ans,ans+n+1,0);
for(auto i:f) ans[abs(i.fi.fi-i.fi.se)]++;
for(i=0;i<n;i++) printf("%d%c",ans[i]," \n"[i==n-1]);
}
int main(){
int t=1;
scanf("%d",&t);
while(t--) Solve();
cerr<<clock()*1.0/CLOCKS_PER_SEC<<'\n';
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 24492kb
input:
4 2 1 2 2 1 5 2 4 1 5 3 2 4 1 5 3 5 1 2 3 4 5 5 4 3 2 1 8 5 8 3 4 2 7 1 6 4 6 3 8 5 1 2 7
output:
2 0 5 0 0 0 0 2 2 2 2 0 5 5 2 2 1 0 0 0
result:
ok 20 numbers
Test #2:
score: 0
Accepted
time: 587ms
memory: 10144kb
input:
66664 7 4 2 6 5 7 1 3 6 5 3 1 4 7 2 10 6 8 10 7 5 1 4 3 9 2 5 10 3 8 6 7 2 9 1 4 9 3 2 4 8 7 6 9 1 5 8 1 2 9 6 7 4 3 5 10 4 3 9 6 7 2 10 1 8 5 3 5 4 1 2 7 10 9 6 8 5 3 4 1 2 5 5 1 3 2 4 5 2 4 3 5 1 2 3 1 4 5 6 2 6 1 3 4 5 6 4 5 1 3 2 10 10 1 2 7 5 8 4 3 9 6 9 4 2 3 6 1 7 8 5 10 5 1 2 4 5 3 4 1 2 5 3...
output:
4 4 2 2 1 0 0 5 6 3 2 2 1 0 0 0 0 5 6 3 2 1 0 0 0 0 4 4 4 3 2 1 0 0 0 0 5 3 0 0 0 2 2 2 2 0 3 3 3 1 0 0 5 7 4 2 1 0 0 0 0 0 5 2 0 0 0 6 3 0 0 0 0 3 3 2 0 0 5 4 2 1 0 0 0 3 2 3 1 0 0 4 6 3 0 0 0 0 3 4 3 2 1 0 0 3 2 2 2 2 2 2 1 0 4 5 3 1 0 0 0 3 4 3 2 3 3 1 0 0 0 8 5 0 0 0 0 0 0 7 8 3 1 0 0 0 0 0 0 5 ...
result:
ok 499999 numbers
Test #3:
score: 0
Accepted
time: 1417ms
memory: 22460kb
input:
6690 72 31 50 47 60 24 33 72 49 5 26 17 65 40 64 8 2 19 51 30 58 71 16 66 56 9 48 21 61 44 59 22 11 15 28 68 29 1 27 37 41 23 6 20 62 43 34 18 4 70 54 13 12 36 35 25 67 45 38 69 53 42 63 55 3 14 7 57 32 52 39 10 46 31 9 7 56 32 64 39 33 62 24 49 54 18 53 43 40 4 28 37 2 61 47 10 26 23 16 22 30 11 60...
output:
7 11 7 5 6 6 5 4 4 4 4 4 4 4 4 4 4 4 4 4 4 4 3 2 2 2 3 4 4 4 4 4 3 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 4 6 6 4 4 3 2 2 2 2 2 2 2 2 2 3 4 4 4 4 4 3 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 4 6 6 7 8 7 6 7 8 8 7 5 4 4 3 2 2 2 2...
result:
ok 499981 numbers
Test #4:
score: 0
Accepted
time: 2236ms
memory: 22588kb
input:
666 775 98 357 198 407 409 200 454 585 319 622 366 264 710 91 765 78 32 528 335 101 469 204 312 382 276 613 231 342 327 324 441 544 413 299 494 393 349 611 211 702 165 297 320 284 401 530 317 567 142 742 447 482 662 126 506 273 362 328 555 416 206 604 589 305 99 114 291 131 386 75 670 280 704 189 43...
output:
11 20 20 20 19 18 18 18 18 18 18 18 18 18 18 18 18 17 16 16 16 16 16 16 16 16 16 16 16 16 16 15 14 14 14 14 13 12 12 12 12 12 12 12 12 11 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 9 8 8 8 8 7 6 6 6 6 6 6 6 6 6 6 6 6 ...
result:
ok 500000 numbers
Test #5:
score: 0
Accepted
time: 2928ms
memory: 24552kb
input:
65 9836 5216 2035 5946 2744 9708 9116 1184 2000 4650 569 2428 585 3406 8146 6809 875 9131 9092 5998 2088 8393 9447 7766 4990 3903 7730 3426 6726 2029 4208 1546 4639 997 1428 2357 8630 7552 3531 7241 3530 4548 7310 3205 3508 9764 8929 4781 5702 3777 670 7384 1049 1707 4544 1637 9349 2427 3338 634 596...
output:
8 13 12 11 10 10 10 10 10 11 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 12 10 8 8 8 8 8 8 8 8 8 7 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6 6...
result:
ok 500000 numbers
Test #6:
score: 0
Accepted
time: 3936ms
memory: 38372kb
input:
10 50000 41908 17741 2708 24703 42556 45152 20315 17143 16957 48829 30280 7534 9806 2455 27752 28698 34180 30641 1976 19099 8271 18233 1745 46600 1241 19569 3867 840 10336 49514 49491 43521 26857 2277 9054 3016 41237 15468 48237 37950 17442 44525 46971 40928 34005 15252 14887 48465 26039 13079 40736...
output:
14 26 24 23 22 20 19 18 18 18 18 18 18 18 18 17 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 16 ...
result:
ok 500000 numbers
Test #7:
score: 0
Accepted
time: 4362ms
memory: 50388kb
input:
5 100000 70435 82297 64478 96762 51480 50092 4607 731 51337 24967 98580 69079 26300 41515 57826 4744 92883 9657 3287 12443 17262 15832 41138 53280 53542 76263 69136 64644 83006 75161 76406 36134 88895 42403 28621 24815 35829 8899 38986 16475 15367 82413 56456 17355 21826 58017 2762 62100 53594 63010...
output:
18 35 35 34 32 30 29 28 28 28 27 26 25 24 24 24 24 24 23 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 22 ...
result:
ok 500000 numbers
Test #8:
score: -100
Time Limit Exceeded
input:
1 500000 288678 283027 462112 250066 400523 251310 197889 338696 246896 186409 257754 49529 168322 411341 237155 355566 411724 493312 55378 447538 212152 404975 126509 127651 69151 318513 199941 486793 15909 363053 288273 492124 313983 118718 165238 332535 415290 337782 365660 206063 123709 273038 4...