Submission #30091

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
30091	2017-07-22T05:40:24 Z	khsoo01	Temperature (POI11_tem)	C++11	100 / 100	666 ms	25456 KB

#include<bits/stdc++.h>
using namespace std;
typedef pair<int,int> pii;
const int N = 1000005;

int n, s[N], e[N], l[N], ans;

vector<pii> st;

struct segtree {
	int v[3*N], lim;
	void init (int T[]) {
		for(lim=1;lim<=n+1;lim<<=1);
		for(int i=1;i<=n;i++) v[i+lim] = T[i];
		for(int i=lim;--i;) v[i] = max(v[2*i], v[2*i+1]);
	}
	int lb (int P, int V) {
		P += lim;
		while(P&(P+1)) {
			if(v[P] > V) break;
			P = (P-1)/2;
		}
		if(!(P&(P+1))) return 0;
		while(P < lim) {
			P = 2*P + (v[2*P+1] > V);
		}
		return P - lim;
	}
	int rb (int P, int V) {
		P += lim;
		while(P&(P-1)) {
			if(v[P] > V) break;
			P = (P+1)/2;
		}
		if(!(P&(P-1))) return n+1;
		while(P < lim) {
			P = 2*P + !(v[2*P] > V);
		}
		return P - lim;
	}
} seg;

int main()
{
	scanf("%d",&n);
	for(int i=1;i<=n;i++) {
		scanf("%d%d",&s[i],&e[i]);
	}
	seg.init(s);
	for(int i=1;i<=n;i++) {
		l[i] = seg.lb(i, e[i]) + 1;
	}
	seg.init(l);
	for(int i=1;i<=n;i++) {
		ans = max(ans, seg.rb(i, i) - i);
	}
	printf("%d\n",ans);
}

Compilation message

tem.cpp: In function 'int main()':
tem.cpp:45:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&n);
                ^
tem.cpp:47:28: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d",&s[i],&e[i]);
                            ^

Subtask #1
8.0 / 8.0

#	Verdict	Memory	Grader output
1	Correct	25456 KB	Output is correct
2	Correct	25456 KB	Output is correct
3	Correct	25456 KB	Output is correct

Subtask #2
8.0 / 8.0

#	Verdict	Memory	Grader output
1	Correct	25456 KB	Output is correct
2	Correct	25456 KB	Output is correct
3	Correct	25456 KB	Output is correct
4	Correct	25456 KB	Output is correct

Subtask #3
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	3 ms	25456 KB	Output is correct
2	Correct	3 ms	25456 KB	Output is correct
3	Correct	0 ms	25456 KB	Output is correct

Subtask #4
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	203 ms	25456 KB	Output is correct
2	Correct	146 ms	25456 KB	Output is correct
3	Correct	229 ms	25456 KB	Output is correct

Subtask #5
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	429 ms	25456 KB	Output is correct
2	Correct	366 ms	25456 KB	Output is correct
3	Correct	386 ms	25456 KB	Output is correct

Subtask #6
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	479 ms	25456 KB	Output is correct
2	Correct	429 ms	25456 KB	Output is correct
3	Correct	459 ms	25456 KB	Output is correct

Subtask #7
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	513 ms	25456 KB	Output is correct
2	Correct	319 ms	25456 KB	Output is correct
3	Correct	503 ms	25456 KB	Output is correct

Subtask #8
8.0 / 8.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	439 ms	25456 KB	Output is correct
2	Correct	339 ms	25456 KB	Output is correct
3	Correct	333 ms	25456 KB	Output is correct

Subtask #9
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	283 ms	25456 KB	Output is correct
2	Correct	323 ms	25456 KB	Output is correct
3	Correct	286 ms	25456 KB	Output is correct

Subtask #10
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	353 ms	25456 KB	Output is correct
2	Correct	293 ms	25456 KB	Output is correct

Subtask #11
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	416 ms	25456 KB	Output is correct
2	Correct	666 ms	25456 KB	Output is correct

Subtask #12
9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	436 ms	25456 KB	Output is correct
2	Correct	486 ms	25456 KB	Output is correct