oj.uz

답안 #4719

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
4719 2013-12-22T14:46:16 Z ainta 사다리꼴 (balkan11_trapezoid) C++
13 / 100
 79 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;
			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
13.0 / 100.0

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