제출 #20969

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
20969		kdh9949	사다리꼴 (balkan11_trapezoid)	C++14	80 / 100	363 ms	65536 KiB

trapezoid

#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);
}

컴파일 시 표준 에러 (stderr) 메시지

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 / 100