답안 #875950

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
875950	2023-11-20T20:34:03 Z	Lobo	Boat (APIO16_boat)	C++17	31 / 100	2000 ms	191008 KB

boat

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define fr first
#define sc second
const int maxn = 1e6+10;
const int maxv = 1e9;
const int lg = 31;
const int mod = 1e9+7;

int n;
int lc[maxn*lg], rc[maxn*lg], tr[maxn*lg], cntno;

int upd(int no, int l, int r, int pos, int val) {
	if(l > pos or r < pos) return no;
	if(no == 0) no = ++cntno;
	if(l == r) {
		tr[no]+= val;
		tr[no]%= mod;
		return no;
	}
	int mid = (l+r)/2;

	lc[no] = upd(lc[no],l,mid,pos,val);
	rc[no] = upd(rc[no],mid+1,r,pos,val);
	tr[no] = tr[lc[no]]+tr[rc[no]];
	tr[no]%= mod;
	return no;
}

int query(int no, int l, int r, int ll, int rr) {
	if(l > rr or r < ll or no == 0) return 0;
	if(l >= ll && r <= rr) return tr[no];
	int mid = (l+r)/2;
	return (query(lc[no],l,mid,ll,rr)+query(rc[no],mid+1,r,ll,rr))%mod;
}

int32_t main() {
	cin >> n;

	int rt = upd(0,0,maxv,0,1);
	for(int i = 1; i <= n; i++) {
		int a,b; cin >> a >> b;
		for(int j = b; j >= a; j--) {
			upd(rt,0,maxv,j,query(rt,0,maxv,0,j-1));
		}
	}

	cout << query(rt,0,maxv,1,maxv) << endl;
}

Subtask #1

9.0 / 9.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	760 KB	Output is correct
2	Correct	1 ms	604 KB	Output is correct
3	Correct	1 ms	604 KB	Output is correct
4	Correct	1 ms	604 KB	Output is correct
5	Correct	1 ms	604 KB	Output is correct
6	Correct	1 ms	600 KB	Output is correct
7	Correct	1 ms	604 KB	Output is correct
8	Correct	1 ms	604 KB	Output is correct
9	Correct	1 ms	604 KB	Output is correct
10	Correct	1 ms	604 KB	Output is correct
11	Correct	1 ms	604 KB	Output is correct
12	Correct	1 ms	604 KB	Output is correct
13	Correct	1 ms	604 KB	Output is correct
14	Correct	1 ms	604 KB	Output is correct
15	Correct	1 ms	604 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Correct	2 ms	348 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	1 ms	344 KB	Output is correct

Subtask #2

22.0 / 22.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	760 KB	Output is correct
2	Correct	1 ms	604 KB	Output is correct
3	Correct	1 ms	604 KB	Output is correct
4	Correct	1 ms	604 KB	Output is correct
5	Correct	1 ms	604 KB	Output is correct
6	Correct	1 ms	600 KB	Output is correct
7	Correct	1 ms	604 KB	Output is correct
8	Correct	1 ms	604 KB	Output is correct
9	Correct	1 ms	604 KB	Output is correct
10	Correct	1 ms	604 KB	Output is correct
11	Correct	1 ms	604 KB	Output is correct
12	Correct	1 ms	604 KB	Output is correct
13	Correct	1 ms	604 KB	Output is correct
14	Correct	1 ms	604 KB	Output is correct
15	Correct	1 ms	604 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Correct	2 ms	348 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	1 ms	344 KB	Output is correct
21	Correct	438 ms	600 KB	Output is correct
22	Correct	431 ms	684 KB	Output is correct
23	Correct	409 ms	600 KB	Output is correct
24	Correct	450 ms	676 KB	Output is correct
25	Correct	454 ms	848 KB	Output is correct
26	Correct	474 ms	592 KB	Output is correct
27	Correct	484 ms	852 KB	Output is correct
28	Correct	483 ms	604 KB	Output is correct
29	Correct	493 ms	612 KB	Output is correct
30	Correct	512 ms	47084 KB	Output is correct
31	Correct	506 ms	45952 KB	Output is correct
32	Correct	527 ms	46708 KB	Output is correct
33	Correct	503 ms	45584 KB	Output is correct
34	Correct	499 ms	45908 KB	Output is correct
35	Correct	476 ms	43812 KB	Output is correct
36	Correct	494 ms	45448 KB	Output is correct
37	Correct	498 ms	45856 KB	Output is correct
38	Correct	486 ms	44628 KB	Output is correct

Subtask #3

0 / 27.0

#	결과	실행 시간	메모리	Grader output
1	Execution timed out	2095 ms	191008 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #4

0 / 42.0

#	결과	실행 시간	메모리	Grader output
1	Correct	1 ms	760 KB	Output is correct
2	Correct	1 ms	604 KB	Output is correct
3	Correct	1 ms	604 KB	Output is correct
4	Correct	1 ms	604 KB	Output is correct
5	Correct	1 ms	604 KB	Output is correct
6	Correct	1 ms	600 KB	Output is correct
7	Correct	1 ms	604 KB	Output is correct
8	Correct	1 ms	604 KB	Output is correct
9	Correct	1 ms	604 KB	Output is correct
10	Correct	1 ms	604 KB	Output is correct
11	Correct	1 ms	604 KB	Output is correct
12	Correct	1 ms	604 KB	Output is correct
13	Correct	1 ms	604 KB	Output is correct
14	Correct	1 ms	604 KB	Output is correct
15	Correct	1 ms	604 KB	Output is correct
16	Correct	1 ms	348 KB	Output is correct
17	Correct	1 ms	348 KB	Output is correct
18	Correct	2 ms	348 KB	Output is correct
19	Correct	1 ms	348 KB	Output is correct
20	Correct	1 ms	344 KB	Output is correct
21	Correct	438 ms	600 KB	Output is correct
22	Correct	431 ms	684 KB	Output is correct
23	Correct	409 ms	600 KB	Output is correct
24	Correct	450 ms	676 KB	Output is correct
25	Correct	454 ms	848 KB	Output is correct
26	Correct	474 ms	592 KB	Output is correct
27	Correct	484 ms	852 KB	Output is correct
28	Correct	483 ms	604 KB	Output is correct
29	Correct	493 ms	612 KB	Output is correct
30	Correct	512 ms	47084 KB	Output is correct
31	Correct	506 ms	45952 KB	Output is correct
32	Correct	527 ms	46708 KB	Output is correct
33	Correct	503 ms	45584 KB	Output is correct
34	Correct	499 ms	45908 KB	Output is correct
35	Correct	476 ms	43812 KB	Output is correct
36	Correct	494 ms	45448 KB	Output is correct
37	Correct	498 ms	45856 KB	Output is correct
38	Correct	486 ms	44628 KB	Output is correct
39	Execution timed out	2095 ms	191008 KB	Time limit exceeded
40	Halted	0 ms	0 KB	-