QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#38870#3310. Steel Slicing 2wind_whisperWA 9ms20712kbC++142.1kb2022-07-07 20:49:332022-07-07 20:49:34

Judging History

你现在查看的是最新测评结果

  • [2023-08-10 23:21:45]
  • System Update: QOJ starts to keep a history of the judgings of all the submissions.
  • [2022-07-07 20:49:34]
  • 评测
  • 测评结果:WA
  • 用时:9ms
  • 内存:20712kb
  • [2022-07-07 20:49:33]
  • 提交

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;
}

Details

Tip: Click on the bar to expand more detailed information

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'