oj.uz

답안 #4722

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
4722 2013-12-22T14:56:40 Z ainta 사다리꼴 (balkan11_trapezoid) C++
25 / 100
 96 ms 7408 KB 
#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[301000];
struct trapezoid{
	int a, b, c, d;
	bool operator <(const trapezoid &p)const{
		return b < p.b;
	}
}w[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 < 2 * 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++){
		while (w[i].a>w[pv].b){
			ins(SZ+w[pv].d, pv+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

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
25.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 7408 KB Output is correct
2 Correct 0 ms 7408 KB Output is correct
3 Incorrect 0 ms 7408 KB Output isn't correct
4 Correct 0 ms 7408 KB Output is correct
5 Incorrect 0 ms 7408 KB Output isn't correct
6 Incorrect 0 ms 7408 KB Output isn't correct
7 Correct 3 ms 7408 KB Output is correct
8 Incorrect 3 ms 7408 KB Output isn't correct
9 Incorrect 9 ms 7408 KB Output isn't correct
10 Correct 16 ms 7408 KB Output is correct
11 Incorrect 19 ms 7408 KB Output isn't correct
12 Incorrect 53 ms 7408 KB Output isn't correct
13 Incorrect 66 ms 7408 KB Output isn't correct
14 Runtime error 63 ms 7408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 73 ms 7408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 66 ms 7408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 69 ms 7408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 73 ms 7408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 96 ms 7408 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 86 ms 7408 KB Execution killed with signal 11 (could be triggered by violating memory limits)