QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#38870 | #3310. Steel Slicing 2 | wind_whisper | WA | 9ms | 20712kb | C++14 | 2.1kb | 2022-07-07 20:49:33 | 2022-07-07 20:49:34 |
Judging History
answer
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ULL unsigned ll
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug("OK\n")
inline ll read() {
ll x(0),f(1);char c=getchar();
while(!isdigit(c)) {if(c=='-') f=-1;c=getchar();}
while(isdigit(c)) {x=(x<<1)+(x<<3)+c-'0';c=getchar();}
return x*f;
}
const int N=3e5+100;
const int mod=998244353;
const ll inf=1e9;
bool mem1;
bool Flag=0;
int n,m;
struct ST{
int mi[20],lg[N],mn[N][20];
void init(int n,int *a){
lg[0]=-1;
for(int i=1;i<=n;i++) lg[i]=lg[i>>1]+1;
mi[0]=1;
for(int i=1;i<=lg[n];i++) mi[i]=mi[i-1]<<1;
for(int i=1;i<=n;i++) mn[i][0]=a[i];
for(int k=1;k<=lg[n];k++){
for(int i=1;i+mi[k]-1<=n;i++) mn[i][k]=min(mn[i][k-1],mn[i+mi[k-1]][k-1]);
}
return;
}
inline int Min(int l,int r){
int k=lg[r-l+1];
return min(mn[l][k],mn[r-mi[k]+1][k]);
}
}H,L;
int h[N],l[N];
int res;
vector<int>seg[N];
int pt[N];
int lst[N<<2];
priority_queue<int,vector<int>,greater<int> >q;
int main(){
#ifndef ONLINE_JUDGE
freopen("a.in","r",stdin);
freopen("a.out","w",stdout);
#endif
n=read();
for(int i=1;i<=n;i++){
h[i]=read();
l[i]=read();
}
H.init(n,h);
L.init(n,l);
for(int i=1;i<=n;i++){
int p=lst[h[i]];
//printf("p=%d min=%d\n",p,H.Min(p+1,i-1));
if(p&&p<i-1&&H.Min(p+1,i-1)>=h[i]){
seg[p].push_back(i-1);
++res;
//printf("%d %d\n",p,i-1);
}
lst[h[i]]=i;
}
memset(lst,0,sizeof(lst));
for(int i=1;i<=n;i++){
int p=lst[l[i]];
if(p&&p<i-1&&L.Min(p+1,i-1)>=l[i]){
seg[p].push_back(i-1);
++res;
//printf("%d %d\n",p,i-1);
}
lst[l[i]]=i;
}
int ans(0);
for(int i=1;i<n;i++){
ans+=h[i]!=h[i+1];
ans+=l[i]!=l[i+1];
//printf(" i=%d ans=%d %d %d\n",i,ans);
if(h[i]!=h[i+1]&&l[i]!=l[i+1]){
++res;
pt[i]=1;
}
}
//printf("ans=%d\n",ans);
for(int i=1;i<=n;i++){
while(!q.empty()&&q.top()<i) q.pop();
for(int x:seg[i]) q.push(i);
if(pt[i]){
if(!q.empty()){
q.pop();
res--;
}
}
}
ans-=res;
printf("%d\n",ans);
return 0;
}
詳細信息
Test #1:
score: 100
Accepted
time: 3ms
memory: 20652kb
input:
8 1 4 4 2 3 2 5 1 6 4 4 2 2 3 5 1
output:
7
result:
ok single line: '7'
Test #2:
score: 0
Accepted
time: 4ms
memory: 20500kb
input:
5 23 15 23 17 3 22 15 3 5 1
output:
4
result:
ok single line: '4'
Test #3:
score: 0
Accepted
time: 5ms
memory: 20080kb
input:
8 1 2 2 2 2 1 1 1 1 2 2 2 2 2 1 2
output:
4
result:
ok single line: '4'
Test #4:
score: 0
Accepted
time: 9ms
memory: 20368kb
input:
2 1 1000000 1000000 1
output:
1
result:
ok single line: '1'
Test #5:
score: 0
Accepted
time: 2ms
memory: 20500kb
input:
1 1 1
output:
0
result:
ok single line: '0'
Test #6:
score: 0
Accepted
time: 2ms
memory: 20620kb
input:
1000 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1...
output:
0
result:
ok single line: '0'
Test #7:
score: -100
Wrong Answer
time: 0ms
memory: 20712kb
input:
1000 2 1 2 1 1 2 1 2 1 2 1 2 2 2 1 1 1 2 1 2 1 1 1 2 2 1 1 1 1 2 2 2 1 1 2 2 1 2 1 2 2 1 2 1 1 2 1 1 1 2 2 2 2 1 2 2 1 2 2 1 1 2 1 2 2 2 1 2 1 2 2 2 2 1 2 1 2 1 1 2 2 1 2 2 1 1 1 2 2 2 2 1 1 1 1 1 2 1 2 2 2 2 1 1 1 1 1 1 1 1 2 1 2 2 1 2 2 1 2 2 1 1 2 2 2 1 2 1 1 1 2 1 2 1 2 1 1 2 1 1 2 1 2 1 2 1 2 2...
output:
438
result:
wrong answer 1st lines differ - expected: '505', found: '438'