Submission #20558

#	Time	Username	Problem	Language	Result	Execution time	Memory
20558		CodingAmolang (#35)	초음속철도 (OJUZ11_rail)	C++11	70 / 100	3000 ms	12752 KiB

rail

#include<stdio.h>
#include<vector>
#include<algorithm>
#include<queue>
#include<string.h>
using std::queue;
using std::vector;
const long long MOD = 1000000007;
using std::pair;
long long di[400100];
int sz = 800;
long long start[1000];
long long end[1000];
int cnt[1000];
long long sum[1000];
long long arr[400100];

long long poww(long long a, long long b) {
	if (b == 0)return 1;
	long long tmp = poww(a, b / 2);
	if (b % 2 == 1)return (((tmp*tmp) % MOD)*a) % MOD;
	return (tmp*tmp) % MOD;
}
int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	vector<int> X = { 1,n };
	vector<pair<int, int>> seg;
	for (int i = 0; i < m; i++) {
		int s, e;
		scanf("%d%d", &s, &e);
		seg.push_back({ s,e });
		X.push_back(s);
		X.push_back(e);
	}
	std::sort(seg.begin(), seg.end());
	std::sort(X.begin(), X.end());
	X.erase(std::unique(X.begin(), X.end()), X.end());
	memset(start, 0xff, sizeof(start));
	for (int i = 0; i < X.size(); i++) {
		di[i] = i / sz;
		if (start[di[i]] == -1)start[di[i]] = i;
		end[di[i]] = i;
	}
	sum[di[0]]++;
	arr[0]++;
	for (auto segment : seg) {
		int s = std::lower_bound(X.begin(), X.end(), segment.first) - X.begin();
		int e = std::lower_bound(X.begin(), X.end(), segment.second) - X.begin();
		long long S = 0;
		for (int i = s; i <= e; i++) {
			if (start[di[i]] == i && end[di[i]]<=e) {
				S += sum[di[i]];
				S %= MOD;
				i = end[di[i]];
				continue;
			}
			else if(cnt[di[i]]!=0){
				for (int k = start[di[i]]; k <= end[di[i]]; k++) {
					arr[k] *= poww(2, cnt[di[k]]);
					arr[k] %= MOD;
				}
				cnt[di[i]] = 0;
			}
			S += arr[i];
			S %= MOD;

		}
		if (cnt[di[e]] != 0) {
			for (int i = start[di[e]]; i <= end[di[e]]; i++) {
				arr[i] *=poww(2,cnt[di[i]]);
				arr[i] %= MOD;
			}
			cnt[di[e]] = 0;
		}
		arr[e] += S;
		arr[e] %= MOD;
		sum[di[e]] += S;
		sum[di[e]] %= MOD;
		for (int i = e + 1; i <= X.size() - 1; i++) {
			if (start[di[i]] == i && end[di[i]] <= X.size()-1) {
				cnt[di[i]]++;
				sum[di[i]] *= 2;
				sum[di[i]] %= MOD;
				i = end[di[i]];
				continue;
			}
			sum[di[i]] += arr[i];
			sum[di[i]] %= MOD;
			arr[i] *= 2;
			arr[i] %= MOD;
		}
	}
	arr[X.size() - 1] *= poww(2,cnt[di[X.size()-1]]) % MOD;
	arr[X.size() - 1] %= MOD;
	printf("%lld", arr[X.size() - 1]);
}

Compilation message (stderr)

rail.cpp: In function 'int main()':
rail.cpp:40:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for (int i = 0; i < X.size(); i++) {
                    ^
rail.cpp:80:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for (int i = e + 1; i <= X.size() - 1; i++) {
                         ^
rail.cpp:81:40: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    if (start[di[i]] == i && end[di[i]] <= X.size()-1) {
                                        ^
rail.cpp:26:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &n, &m);
                       ^
rail.cpp:31:24: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &s, &e);
                        ^

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