oj.uz

답안 #20969

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
20969 2017-03-25T11:42:41 Z kdh9949 사다리꼴 (balkan11_trapezoid) C++14
80 / 100
 363 ms 65536 KB 
#include <bits/stdc++.h>
using namespace std;

struct Rect{
	int us, ue;
	int ds, de;
	bool operator<(const Rect &oth) const {
		return ue < oth.ue;
	}
}a[100001];

int n;
int ux[200002], dx[200002];

struct Node{
	Node *l, *r;
	pair<int, int> data;
	Node() : l(NULL), r(NULL), data({0, 1}) {}
}*tree[100001];

pair<int, int> merge(pair<int, int> x, pair<int, int> y){
	if(x.first == y.first) return {x.first, x.first ? (x.second + y.second) % 30013 : 1};
	return max(x, y);
}

void init(Node *cur, int s, int e){
    cur->data = {0, 1};
    if(s == e) return;
    cur->l = new Node();
    cur->r = new Node();
    init(cur->l, s, (s+e)/2);
    init(cur->r, (s+e)/2 + 1, e);
}

Node* make_tree(Node *cur, int s, int e, int x, pair<int, int> v){
    if(x < s || e < x) return cur;
    Node *ret = new Node();
    if(s == e){
		ret->data = v;
		return ret;
    }
    ret->l = make_tree(cur->l, s, (s+e)/2, x, v);
    ret->r = make_tree(cur->r, (s+e)/2 + 1, e, x, v);
    ret->data = merge(ret->l->data, ret->r->data);
    return ret;
}

pair<int, int> query(Node *cur, int s, int e, int x, int y){
	if(e < x || y < s) return {0, 1};
	if(x <= s && e <= y) return cur->data;
	return merge(query(cur->l, s, (s+e)/2, x, y),
				 query(cur->r, (s+e)/2 + 1, e, x, y));
}

int main(){
	scanf("%d", &n);
	for(int i = 1; i <= n; i++){
		int us, ue, ds, de;
		scanf("%d%d%d%d", &us, &ue, &ds, &de);
		ux[2 * i - 1] = us;
		ux[2 * i] = ue;
		dx[2 * i - 1] = ds;
		dx[2 * i] = de;
        a[i] = {us, ue, ds, de};
	}
	sort(ux + 1, ux + 2 * n + 1);
	sort(dx + 1, dx + 2 * n + 1);
    for(int i = 1; i <= n; i++){
		a[i].us = lower_bound(ux + 1, ux + 2 * n + 1, a[i].us) - ux;
		a[i].ue = lower_bound(ux + 1, ux + 2 * n + 1, a[i].ue) - ux;
		a[i].ds = lower_bound(dx + 1, dx + 2 * n + 1, a[i].ds) - dx;
		a[i].de = lower_bound(dx + 1, dx + 2 * n + 1, a[i].de) - dx;
    }
    sort(a + 1, a + n + 1);
    tree[0] = new Node();
    init(tree[0], 1, 2 * n);
	for(int i = 1; i <= n; i++){
		int t = lower_bound(a + 1, a + n + 1, (Rect){0, a[i].us, 0, 0}) - a - 1;
		pair<int, int> x = query(tree[t], 1, 2 * n, 1, a[i].ds);
		tree[i] = make_tree(tree[i - 1], 1, 2 * n, a[i].de, {x.first + 1, x.second});
	}
	printf("%d %d\n", tree[n]->data.first, tree[n]->data.second);
}

Compilation message

trapezoid.cpp: In function 'int main()':
trapezoid.cpp:56:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &n);
                 ^
trapezoid.cpp:59:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &us, &ue, &ds, &de);
                                        ^

Subtask #1
80.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 5928 KB Output is correct
2 Correct 0 ms 5928 KB Output is correct
3 Correct 0 ms 6192 KB Output is correct
4 Correct 0 ms 6456 KB Output is correct
5 Correct 3 ms 6984 KB Output is correct
6 Correct 0 ms 7644 KB Output is correct
7 Correct 3 ms 8172 KB Output is correct
8 Correct 9 ms 8832 KB Output is correct
9 Correct 29 ms 12000 KB Output is correct
10 Correct 53 ms 18732 KB Output is correct
11 Correct 79 ms 22164 KB Output is correct
12 Correct 169 ms 39852 KB Output is correct
13 Correct 216 ms 46980 KB Output is correct
14 Correct 269 ms 54372 KB Output is correct
15 Correct 306 ms 58068 KB Output is correct
16 Correct 363 ms 61896 KB Output is correct
17 Memory limit exceeded 313 ms 65536 KB Memory limit exceeded
18 Memory limit exceeded 239 ms 65536 KB Memory limit exceeded
19 Memory limit exceeded 289 ms 65536 KB Memory limit exceeded
20 Memory limit exceeded 329 ms 65536 KB Memory limit exceeded