QOJ.ac
QOJ
| ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
|---|---|---|---|---|---|---|---|---|---|
| #105293 | #6134. Soldier Game | Sorting# | AC ✓ | 468ms | 13248kb | C++ | 1.5kb | 2023-05-13 21:06:47 | 2023-05-13 21:06:48 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
const int N=2e5+1;
#define fi first
#define se second
int n,k;
ll a[100001];
const int ts=262144;
pair<ll,int>st[2*N];
int can[ts][2][2];
void pull(int id){
for(int i=0; i<2 ;i++){
for(int j=0; j<2 ;j++){
can[id][i][j]=0;
for(int k=0; k<2 ;k++){
can[id][i][j]|=can[id*2][i][k]*can[id*2+1][k][j];
}
}
}
}
void build(int id,int l,int r){
if(l==r){
can[id][0][0]=can[id][0][1]=can[id][1][1]=0;
can[id][1][0]=1;
return;
}
int mid=(l+r)/2;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
pull(id);
}
void upd(int id,int l,int r,int p,int t,int v){
//if(id==1) cout << "upd " << p << ' ' << t << ' ' << v << endl;
if(l==r){
if(t==1) can[id][0][1]=v;
else can[id][1][1]=v;
return;
}
int mid=(l+r)/2;
if(p<=mid) upd(id*2,l,mid,p,t,v);
else upd(id*2+1,mid+1,r,p,t,v);
pull(id);
}
void solve(){
cin >> n;
for(int i=1; i<=n ;i++){
cin >> a[i];
st[2*i-1]={a[i],2*i};
if(i>1) st[2*i-2]={a[i]+a[i-1],2*i-1};
}
sort(st+1,st+2*n);
build(1,1,n);
int l=1;
ll ans=2e18;
for(int i=1; i<=2*n-1 ;i++){
upd(1,1,n,(st[i].se+1)/2,st[i].se%2,1);
while(can[1][1][1]){
//cout << "can " << st[l].fi << ' ' << st[i].fi << endl;
upd(1,1,n,(st[l].se+1)/2,st[l].se%2,0);
l++;
}
if(l>1) ans=min(ans,st[i].fi-st[l-1].fi);
}
cout << ans << '\n';
}
int main(){
ios::sync_with_stdio(false);cin.tie(0);
int t;cin >> t;
while(t--) solve();
}
详细
Test #1:
score: 100
Accepted
time: 0ms
memory: 5404kb
input:
3 5 -1 4 2 1 1 4 1 3 2 4 1 7
output:
1 2 0
result:
ok 3 number(s): "1 2 0"
Test #2:
score: 0
Accepted
time: 423ms
memory: 13248kb
input:
10010 1 1000000000 1 -1000000000 2 1000000000 -1000000000 4 1000000000 1000000000 -1000000000 -1000000000 3 100 -100 100 16 -17 91 -19 66 100 -70 -71 76 -58 99 52 19 25 -67 -63 -32 7 -95 -26 63 -55 -19 77 -100 17 -100 72 -53 -32 8 -100 53 44 -100 -65 -81 -59 100 100 57 -47 1 11 99 10 -100 3 32 2 -26...
output:
0 0 0 2000000000 100 135 103 181 189 84 63 164 176 0 147 135 152 36 200 131 134 0 136 0 72 171 146 0 183 77 176 89 200 135 38 109 119 126 158 189 70 0 38 999804364 188 161 0 116 116 200 0 101 200 39 0 183 139 0 183 107 139 0 178 85993 126 153 168 163 96 53 96 52 126 47 130 79 0 123 188 173 33 0 83 1...
result:
ok 10010 numbers
Test #3:
score: 0
Accepted
time: 61ms
memory: 11332kb
input:
1 100000 -999999999 999999999 999999998 -999999998 -999999997 999999997 999999996 -999999996 999999995 -999999995 -999999994 999999994 -999999993 999999993 -999999992 999999992 -999999991 999999991 999999990 -999999990 999999989 -999999989 999999988 -999999988 999999987 -999999987 999999986 -9999999...
output:
0
result:
ok 1 number(s): "0"
Test #4:
score: 0
Accepted
time: 468ms
memory: 11356kb
input:
10011 1 1000000000 1 -1000000000 2 1000000000 -1000000000 4 1000000000 1000000000 -1000000000 -1000000000 12 48 54 98 -20 -45 56 -100 78 47 23 -100 -21 19 66 41 52 17 -9 -90 -36 90 -26 66 -86 -83 -39 -83 35 78 100 -68 -62 2 -100 -23 17 89 -26 -100 -38 -14 87 32 -100 16 -31 -35 100 73 -61 -100 43 -48...
output:
0 0 0 2000000000 155 168 0 173 137 167 127 25 91 109 176 0 0 173 115 56 66 67 0 1999775909 121 166 128 77 60 146 152 78 172 110 60 200 89 160 200 130 175 79 97 1999891177 122 154 136 164 123 0 175 77 167 76 40 82 79 159 99 141 165 147 158 1999730298 0 179 31 181 192 193 47 91 164 63 65 138 100 168 1...
result:
ok 10011 numbers
Test #5:
score: 0
Accepted
time: 59ms
memory: 11332kb
input:
1 100000 50000 50000 50001 50001 50002 50002 50003 50003 50004 50004 50005 50005 50006 50006 50007 50007 50008 50008 50009 50009 50010 50010 50011 50011 50012 50012 50013 50013 50014 50014 50015 50015 50016 50016 50017 50017 50018 50018 50019 50019 50020 50020 50021 50021 50022 50022 50023 50023 500...
output:
49999
result:
ok 1 number(s): "49999"