Submission #30091

#	Time	Username	Problem	Language	Result	Execution time	Memory
30091		khsoo01	Untitled (POI11_tem)	C++11	100 / 100	666 ms	25456 KiB

Main

#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 (stderr)

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 / 8
• Subtask 2: 8 / 8
• Subtask 3: 8 / 8
• Subtask 4: 8 / 8
• Subtask 5: 8 / 8
• Subtask 6: 8 / 8
• Subtask 7: 8 / 8
• Subtask 8: 8 / 8
• Subtask 9: 9 / 9
• Subtask 10: 9 / 9
• Subtask 11: 9 / 9
• Subtask 12: 9 / 9