Submission #4727

#	Time	Username	Problem	Language	Result	Execution time	Memory
4727		ainta	trapezoid (balkan11_trapezoid)	C++98	100 / 100	119 ms	10548 KiB

trapezoid

#pragma warning(disable:4996)
#include<stdio.h>
#include<algorithm>
#define SZ 262144
using namespace std;
int n, D[101000], D2[101000], Mod = 30013, Cnt;
struct IndexTree{
	int a, b;
}IT[501000];
struct trapezoid{
	int a, b, c, d;
	bool operator <(const trapezoid &p)const{
		return a < p.a;
	}
}w[101000], w2[101000];
struct order{
	int a, b;
	bool operator <(const order &p)const{
		return a < p.a;
	}
}ord[201000];
void ins(int a, int b){
	while (a){
		if (D[IT[a].a] < D[b])IT[a].a = b, IT[a].b = 0;
		if (D[IT[a].a] == D[b])IT[a].b = (IT[a].b + D2[b]) % Mod;
		a >>= 1;
	}
}
int Max(int a, int b){
	int r = 0;
	Cnt = 0;
	while (a <= b){
		if (a & 1){
			if (D[r] < D[IT[a].a])r = IT[a].a, Cnt = 0;
			if (D[r] == D[IT[a].a])Cnt += IT[a].b;
		}
		if (!(b & 1)){
			if (D[r] < D[IT[b].a])r = IT[b].a, Cnt = 0;
			if (D[r] == D[IT[b].a])Cnt += IT[b].b;
		}
		a = (a + 1) >> 1, b = (b - 1) >> 1;
	}
	Cnt %= Mod;
	return D[r];
}
int main()
{
	int i, pv = 0, Res = 0, Res2 = 0;
	scanf("%d", &n);
	for (i = 0; i < n; i++){
		scanf("%d%d%d%d", &w[i].a, &w[i].b, &w[i].c, &w[i].d);
	}
	sort(w, w + n);
	for (i = 0; i < n; i++){
		ord[i * 2].a = w[i].c, ord[i * 2].b = i * 2;
		ord[i * 2 + 1].a = w[i].d, ord[i * 2 + 1].b = i * 2 + 1;
	}
	sort(ord, ord + n * 2);
	for (i = 0; i < 2 * n; i++){
		if (ord[i].b & 1)w[ord[i].b >> 1].d = i;
		else w[ord[i].b >> 1].c = i;
	}
	for (i = 0; i < n; i++){
		w2[i] = w[i];
		swap(w2[i].a, w2[i].b);
		w2[i].c = i;
	}
	sort(w2, w2 + n);
	for (i = 0; i < n; i++){
		while (w[i].a>w2[pv].a){
			ins(SZ+w2[pv].d, w2[pv].c+1);
			pv++;
		}
		D[i + 1] = Max(SZ, SZ + w[i].c) + 1;
		D2[i + 1] = Cnt;
		if (!D2[i + 1])D2[i + 1] = 1;
		if (Res < D[i + 1])Res = D[i + 1], Res2 = 0;
		if (Res == D[i + 1])Res2 = (Res2 + D2[i + 1]) % Mod;
	}
	printf("%d %d\n", Res, Res2);
}

Compilation message (stderr)

trapezoid.cpp:1:0: warning: ignoring #pragma warning  [-Wunknown-pragmas]
 #pragma warning(disable:4996)
 ^
trapezoid.cpp: In function 'int main()':
trapezoid.cpp:49:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
trapezoid.cpp:51:56: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &w[i].a, &w[i].b, &w[i].c, &w[i].d);
                                                        ^

• Subtask 1: 100 / 100