oj.uz

답안 #4721

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
4721 2013-12-22T14:54:31 Z tncks0121 사다리꼴 (balkan11_trapezoid) C++
2 / 100
 143 ms 8636 KB 
#include <stdio.h> 
#include <stdlib.h> 
#include <string.h> 
#include <memory.h> 
#include <math.h> 
#include <assert.h> 
#include <stack> 
#include <queue> 
#include <map> 
#include <set> 
#include <algorithm> 
#include <string> 
#include <functional> 
#include <vector> 
#include <deque> 
#include <utility> 
#include <bitset> 
#include <limits.h>  

using namespace std; 
typedef long long ll; 
typedef unsigned long long llu; 
typedef double lf;
typedef unsigned int uint;
typedef long double llf;
typedef pair<int, int> pii;

const int N_ = 100005;

int N;

struct Segment {
	int a, b, t;
	Segment (int a = 0, int b = 0, int t = 0): a(a), b(b), t(t) { }
	bool operator< (const Segment &s) const { return a != s.a ? a < s.a : b > s.b; }
};

Segment D[N_+N_];
int DN;
int X[N_+N_];

const int MOD = 30013;
const int LEAF = 131072*2;

struct Node {
	int c, p;
	Node (int c = 0, int p = 0): c(c), p(p) { }
	void apply (Node t) {
		if(t.c > c) c = t.c, p = t.p;
		else if(t.c == c) p = (p + t.p) % MOD;
	}
} Tree[N_+N_+LEAF], Table[N_];

void update (int x, int c, int p) {
	x += LEAF;
	if(Tree[x].c < c) Tree[x] = Node(c, p);
	while(x >>= 1) {
		Node &nd = Tree[x];
		Node &l = Tree[x+x], &r = Tree[x+x+1];
		if(l.c == r.c) nd = Node(l.c, (l.p + r.p) % MOD);
		else if(l.c > r.c) nd = l;
		else nd = r;
	}
}

Node get (int en) {
	int st = LEAF+1; en += LEAF;
	Node ret;
	while(st <= en) {
		if((st & 1) == 1) ret.apply(Tree[st]);
		if((en & 1) == 0) ret.apply(Tree[en]);
		st = (st+1) >> 1;
		en = (en-1) >> 1;
	}
	return ret;
}

int main() {
	int i, j, k;

	scanf("%d", &N);
	for(i = 1; i <= N; i++) {
		int a,b,c,d; scanf("%d%d%d%d", &a, &b, &c, &d);
		D[++DN] = Segment(a, b, -i); X[DN] = b;
		D[++DN] = Segment(c, d,  i); X[DN] = d;
	}

	sort(D+1, D+DN+1);
	sort(X+1, X+DN+1);
	
	for(i = 1; i <= DN; i++) {
		Segment &s = D[i];
		s.b = lower_bound(X+1, X+DN+1, s.b) - X;
		if(s.t < 0) { // left
			Table[-s.t] = get(s.b - 1);
			++Table[-s.t].c;
		}else {
			update(s.b, Table[s.t].c, Table[s.t].p);
		}
	}
	
	printf("%d %d\n", get(DN).c, 0);
	return 0;
}

Compilation message

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:79:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j, k;
         ^
trapezoid.cpp:79:12: warning: unused variable 'k' [-Wunused-variable]
  int i, j, k;
            ^
trapezoid.cpp:81:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
                 ^
trapezoid.cpp:83:49: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   int a,b,c,d; scanf("%d%d%d%d", &a, &b, &c, &d);
                                                 ^

Subtask #1
2.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 3 ms 8636 KB Output isn't correct
2 Incorrect 0 ms 8636 KB Output isn't correct
3 Incorrect 3 ms 8636 KB Output isn't correct
4 Incorrect 6 ms 8636 KB Output isn't correct
5 Incorrect 3 ms 8636 KB Output isn't correct
6 Incorrect 3 ms 8636 KB Output isn't correct
7 Incorrect 3 ms 8636 KB Output isn't correct
8 Incorrect 9 ms 8636 KB Output isn't correct
9 Partially correct 13 ms 8636 KB Partially correct
10 Incorrect 26 ms 8636 KB Output isn't correct
11 Incorrect 33 ms 8636 KB Output isn't correct
12 Incorrect 63 ms 8636 KB Output isn't correct
13 Incorrect 76 ms 8636 KB Output isn't correct
14 Incorrect 93 ms 8636 KB Output isn't correct
15 Incorrect 106 ms 8636 KB Output isn't correct
16 Incorrect 123 ms 8636 KB Output isn't correct
17 Incorrect 116 ms 8636 KB Output isn't correct
18 Incorrect 109 ms 8636 KB Output isn't correct
19 Incorrect 119 ms 8636 KB Output isn't correct
20 Incorrect 143 ms 8636 KB Output isn't correct