제출 #1168920

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1168920		Muhammet	Boat (APIO16_boat)	C++17	31 / 100	2105 ms	384844 KiB

boat

#include "bits/stdc++.h"
 
using namespace std;
 
#define ll long long
#define SZ(s) (int)s.size()
 
const int N = 5e2 + 5;
const int N1 = 1e6 + 5;
const int M = 1e9 + 7;
 
int a[N], b[N];
 
ll st[4 * N1];
 
vector <int> v;
 
int upd(int nd, int l, int r, int x, int vl) {
	if(v[l] > x or v[r] < x) return st[nd];
	if(v[l] == v[r]) {
		st[nd] = (st[nd] + vl);
		if(st[nd] >= M) st[nd] -= M;
		return st[nd];
	}
	int md = (l + r) / 2;
	st[nd] = (upd(nd*2, l, md, x, vl) + upd(nd*2+1, md+1, r, x, vl));
	if(st[nd] >= M) st[nd] -= M;
	return st[nd];
}
 
int fnd(int nd, int l, int r, int x) {
	if(v[l] >= x) return 0;
	if(v[r] < x) return st[nd];
	int md = (l + r) / 2;
	ll y = (fnd(nd*2, l, md, x) + fnd(nd*2+1, md+1, r, x));
	if(y >= M) y -= M;
	return y;
}
 
int main() {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
 
	int n;
	cin >> n;
	set <int> s;
	s.insert(0);
	for(int i = 1; i <= n; i++) {
		cin >> a[i] >> b[i];
		for(int j = a[i]; j <= b[i]; j++) {
			s.insert(j);
		}
	}
	int cnt = 0;
	for(auto i : s) {
		v.push_back(i);
	}
	upd(1, 0, SZ(v)-1, 0, 1);
	ll ans = 0;
	for(int i = 1; i <= n; i++) {
		vector <int> v1;
		for(int j = a[i]; j <= b[i]; j++) {
			v1.push_back(fnd(1, 0, SZ(v)-1, j));
			ans += v1.back();
			if(ans >= M) ans -= M;
		}
		int cn = -1;
		for(int j = a[i]; j <= b[i]; j++) {
			upd(1, 0, SZ(v)-1, j, v1[++cn]);
		}
	}
 
	cout << ans;
 
	return 0;
}

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42