Submission #20389

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

rail

#include <cstdio>
#include <algorithm>

using namespace std;

const int o = 1 << 19, p = 1000000007;

pair<int, int> a[200002];
int t[400004];
int d[1 << 20];
int e[1 << 20];

int main() {
	int i, j, k, n, m, r = 0;
	scanf("%d%d", &t[1], &n);
	if (n > 5000) return 0;
	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;
	d[1] = 1;
	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 = d[a[i].second];
		if (a[i].first == m) r = (r + k) % p;
		for (j = 0; j < a[i].second; j++) d[j] = (d[j] << 1) % p;
		for (j = a[i].second; j <= a[i].first; j++) d[j] = (d[j] + k) % p;
	}
	printf("%d", r);
}

Compilation message (stderr)

rail.cpp: In function 'int main()':
rail.cpp:15: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:19: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: 0 / 25
• Subtask 4: 27 / 27
• Subtask 5: 0 / 30