Submission #4725

#	Time	Username	Problem	Language	Result	Execution time	Memory
4725		tncks0121	trapezoid (balkan11_trapezoid)	C++98	100 / 100	149 ms	8636 KiB

trapezoid

#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, c, -i); X[DN] = b;
		D[++DN] = Segment(b, d,  i); X[DN] = d;
	}

	sort(D+1, D+DN+1);
	sort(X+1, X+DN+1);
	int XN = unique(X+1, X+DN+1) - (X+1);

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

Compilation message (stderr)

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