Submission #20577

#	Time	Username	Problem	Language	Result	Execution time	Memory
20577		G (#35)	초음속철도 (OJUZ11_rail)	C++11	100 / 100	2029 ms	62272 KiB

rail

#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
int n, m;
const int mod = 1000000007;
const int itsz = 1 << 19;
int inp[200100][2];
struct train {
	int s, e;
	bool operator<(const train&r)const {
		return s < r.s;
	}
};
train tl[200100];
long long int it[itsz * 2];
long long int itmult[itsz * 2];
int itrt[itsz * 2];
int itqn;
void itrefresh(int loc) {
	if (itrt[loc] == itqn)return;
	itrt[loc] = itqn;
	if (loc != 1)itrefresh(loc / 2);
	it[loc] *= itmult[loc];
	it[loc] %= mod;
	if (loc < itsz) {
		itmult[loc * 2] *= itmult[loc];
		itmult[loc * 2] %= mod;
		itmult[loc * 2 + 1] *= itmult[loc];
		itmult[loc * 2 + 1] %= mod;
	}
	itmult[loc] = 1;
}
void itbuildup(int loc) {
	if (loc < itsz) {
		it[loc] = it[loc * 2] * itmult[loc * 2] + it[loc * 2 + 1] * itmult[loc * 2 + 1];
		it[loc] %= mod;
	}
	if (loc != 1)itbuildup(loc / 2);
}
void itpush(int loc, int val) {
	itqn++;
	loc += itsz;
	itrefresh(loc);
	it[loc] += val;
	it[loc] %= mod;
	itbuildup(loc);
}
int itcalc(int start, int end) {
	start += itsz;
	end += itsz;
	long long int res = 0;
	while (start <= end) {
		if (start % 2 == 1) {
			itrefresh(start);
			res += it[start];
			res %= mod;
			start++;
		}
		if (end % 2 == 0) {
			itrefresh(end);
			res += it[end];
			res %= mod;
			end--;
		}
		start /= 2;
		end /= 2;
	}
	return res;
}
void itdouble(int start, int end) {
	int ts, te;
	itqn++;
	start += itsz;
	end += itsz;
	ts = start;
	te = end;
	while (start <= end) {
		if (start % 2 == 1) {
			itmult[start] *= 2;
			itmult[start] %= mod;
			start++;
		}
		if (end % 2 == 0) {
			itmult[end] *= 2;
			itmult[end] %= mod;
			end--;
		}
		start /= 2;
		end /= 2;
	}
	start = ts;
	end = te;
	while (start <= end) {
		if (start % 2 == 1) {
			itrefresh(start);
			itbuildup(start);
			start++;
		}
		if (end % 2 == 0) {
			itrefresh(end);
			itbuildup(end);
			end--;
		}
		start /= 2;
		end /= 2;
	}
}
int main() {
	scanf("%d%d", &n, &m);
	for (int i = 0; i < m; i++) {
		scanf("%d%d", &inp[i][0], &inp[i][1]);
	}
	std::set<int> sp;
	std::map<int, int> mp;
	for (int i = 0; i < m; i++) {
		sp.insert(inp[i][0]);
		sp.insert(inp[i][1]);
	}
	sp.insert(1);
	sp.insert(n);
	int cnt = 0;
	for (auto &i : sp) {
		cnt++;
		mp[i] = cnt;
	}
	for (int i = 0; i < m; i++) {
		tl[i].s = mp[inp[i][0]];
		tl[i].e = mp[inp[i][1]];
	}
	std::sort(tl, tl + m);
	itpush(1, 1);
	for (int i = 0; i < m; i++) {
		itpush(tl[i].e, itcalc(tl[i].s, tl[i].e));
		itdouble(tl[i].e + 1, cnt);
	}
	printf("%d", itcalc(cnt, cnt));
	return 0;
}

Compilation message (stderr)

rail.cpp: In function 'int main()':
rail.cpp:110: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:112:40: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &inp[i][0], &inp[i][1]);
                                        ^

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