Submission #31945

#	Time	Username	Problem	Language	Result	Execution time	Memory
31945		junodeveloper	초음속철도 (OJUZ11_rail)	C++14	100 / 100	843 ms	20800 KiB

rail

#include "bits/stdc++.h"
using namespace std;
const int MAXN = 200010;
const int MOD = 1e9 + 7;
int n, m, dp[2 * MAXN + 10];
int T[8 * MAXN], L[8 * MAXN];
pair<int,int> p[MAXN + 1];
vector<int> vx;
void init(int h, int tl, int tr) {
	L[h] = 1;
	if(tl == tr) return;
	int mid = (tl + tr) >> 1;
	init(h * 2, tl, mid);
	init(h * 2 + 1, mid + 1, tr);
}
void push(int h, int tl, int tr) {
	T[h] = (1ll * T[h] * L[h]) % MOD;
	if(tl < tr) {
		L[h * 2] = (1ll * L[h * 2] * L[h]) % MOD;
		L[h * 2 + 1] = (1ll * L[h * 2 + 1] * L[h]) % MOD;
	}
	L[h] = 1;
}
void update1(int h, int tl, int tr, int p, int x) {
	push(h, tl, tr);
	if(tr < p || p < tl) return;
	if(tl == tr) {
		T[h] = (T[h] + x) % MOD;
	} else {
		int mid = (tl + tr) >> 1;
		update1(h * 2, tl, mid, p, x);
		update1(h * 2 + 1, mid + 1, tr, p, x);
		T[h] = (T[h * 2] + T[h * 2 + 1]) % MOD;
	}
}
void update2(int h, int tl, int tr, int l, int r, int x) {
	push(h, tl, tr);
	if(tr < l || r < tl) return;
	if(l <= tl && tr <= r) {
		L[h] = (1ll * L[h] * x) % MOD;
		push(h, tl, tr);
	} else {
		int mid = (tl + tr) >> 1;
		update2(h * 2, tl, mid, l, r, x);
		update2(h * 2 + 1, mid + 1, tr, l, r, x);
		T[h] = (T[h * 2] + T[h * 2 + 1]) % MOD;
	}
}
int query(int h, int tl, int tr, int l, int r) {
	push(h, tl, tr);
	if(tr < l || r < tl) return 0;
	if(l <= tl && tr <= r) return T[h];
	int mid = (tl + tr) >> 1;
	int ql = query(h * 2, tl, mid, l, r);
	int qr = query(h * 2 + 1, mid + 1, tr, l, r);
	return (ql + qr) % MOD;
}
int compress(int x) {
	return (int)(lower_bound(vx.begin(), vx.end(), x) - vx.begin());
}
int main() {
	scanf("%d%d", &n, &m);
	for(int i=1; i<=m; i++) {
		scanf("%d%d", &p[i].first, &p[i].second);
		vx.push_back(p[i].first);
		vx.push_back(p[i].second);
	}
	vx.push_back(1);
	vx.push_back(n);
	sort(vx.begin(), vx.end());
	vx.erase(unique(vx.begin(), vx.end()), vx.end());
	init(1, 0, vx.size() - 1);
	update1(1, 0, vx.size() - 1, 0, 1);
	sort(p + 1, p + m + 1);
	for(int i=1; i<=m; i++) {
		p[i].first = compress(p[i].first);
		p[i].second = compress(p[i].second);
		int qry = query(1, 0, vx.size() - 1, p[i].first, p[i].second);
		update1(1, 0, vx.size() - 1, p[i].second, qry);
		update2(1, 0, vx.size() - 1, p[i].second + 1, vx.size() - 1, 2);
	}
	printf("%d", query(1, 0, vx.size() - 1, vx.size() - 1, vx.size() - 1));
	return 0;
}

Compilation message (stderr)

rail.cpp: In function 'int main()':
rail.cpp:62: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:64:43: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d", &p[i].first, &p[i].second);
                                           ^

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