Submission #20396

#	Time	Username	Problem	Language	Result	Execution time	Memory
20396		윤지학 (#35)	초음속철도 (OJUZ11_rail)	C++98	100 / 100	589 ms	29244 KiB

rail

#include <cstdio>
#include <algorithm>

using namespace std;

const int P = 1000000007;

pair<int, int> a[200002];
int t[400004];

struct tree {
	tree *l, *r;
	int s, e, x, y;
} T[800008];
int Tn;

void Init(tree *p, int s, int e) {
	p->s = s;
	p->e = e;
	p->x = s == 1 && e == 1;
	p->y = 1;
	if (s != e) {
		p->l = T + ++Tn;
		Init(p->l, s, s + e >> 1);
		p->r = T + ++Tn;
		Init(p->r, (s + e >> 1) + 1, e);
	}
}

void Lazy(tree *p) {
	p->l->x = ((long long)p->l->x * p->y + p->x) % P;
	p->l->y = (long long)p->l->y * p->y % P;
	p->r->x = ((long long)p->r->x * p->y + p->x) % P;
	p->r->y = (long long)p->r->y * p->y % P;
	p->y = 1;
	p->x = 0;
}

void Mul(tree *p, int e) {
	if (p->s > e) return;
	if (p->e <= e) {
		p->x = (p->x << 1) % P;
		p->y = (p->y << 1) % P;
		return;
	}
	Lazy(p);
	Mul(p->l, e);
	Mul(p->r, e);
}

void Add(tree *p, int s, int e, int x) {
	if (p->s > e || p->e < s) return;
	if (s <= p->s && p->e <= e) {
		p->x = (p->x + x) % P;
		return;
	}
	Lazy(p);
	Add(p->l, s, e, x);
	Add(p->r, s, e, x);
}

int Get(tree *p, int x) {
	if (p->s == x && p->e == x) return p->x;
	Lazy(p);
	return p->r->s > x ? Get(p->l, x) : Get(p->r, x);
}

int main() {
	int i, j, k, n, m, r = 0;
	scanf("%d%d", &t[1], &n);
	t[0] = 1;
	for (i = 1; i <= n; i++) {
		scanf("%d%d", &t[i << 1], &t[i << 1 | 1]);
		a[i].first = t[i << 1 | 1];
		a[i].second = -t[i << 1];
	}
	sort(a + 1, a + n + 1);
	sort(t, t + n + n + 2);
	m = unique(t, t + n + n + 2) - t;
	Init(T, 0, m);
	for (i = 1; i <= n; i++) {
		a[i].first = upper_bound(t, t + m, a[i].first) - t;
		a[i].second = upper_bound(t, t + m, -a[i].second) - t;
		k = Get(T, a[i].second);
		if (a[i].first == m) r = (r + k) % P;
		Mul(T, a[i].second - 1);
		Add(T, a[i].second, a[i].first, k);
	}
	printf("%d", r);
}

Compilation message (stderr)

rail.cpp: In function 'void Init(tree*, int, int)':
rail.cpp:24:19: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   Init(p->l, s, s + e >> 1);
                   ^
rail.cpp:26:17: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   Init(p->r, (s + e >> 1) + 1, e);
                 ^
rail.cpp: In function 'int main()':
rail.cpp:69:9: warning: unused variable 'j' [-Wunused-variable]
  int i, j, k, n, m, r = 0;
         ^
rail.cpp:70:26: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &t[1], &n);
                          ^
rail.cpp:73:44: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &t[i << 1], &t[i << 1 | 1]);
                                            ^

• Subtask 1: 10 / 10
• Subtask 2: 8 / 8
• Subtask 3: 25 / 25
• Subtask 4: 27 / 27
• Subtask 5: 30 / 30