Submission #105025

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
105025	2019-04-10T08:09:35 Z	puyu_liao	Boat (APIO16_boat)	C++14	31 / 100	2000 ms	127184 KB

boat

#include<bits/stdc++.h>
#include<stdint.h>
using namespace std;
#define IOS {cin.tie(0);ios_base::sync_with_stdio(false);}
#define N 505
#define int int64_t
#define lowbit(x) (x&-x)
const int MOD = 1000000007;

unordered_map<int,int> mp;
void add(int x,int c){
	for(;x<MOD;x+=lowbit(x)) (mp[x] += c) %= MOD;
}

int qur(int x){
	int r = 0;
	for(;x;x-=lowbit(x)) (r += mp[x]) %= MOD;
	return r;
}

int a[N],b[N];	
int32_t main(){
	IOS;
	int n,ans = 0;
	cin >> n;
	for(int i=1;i<=n;i++) cin >> a[i] >> b[i],a[i]++,b[i]++;
	add(1,1);
	for(int i=1;i<=n;i++) {
		for(int j=b[i];j>=a[i];j--) add(j,qur(j-1));
	}
	cout << (qur(MOD-1)+MOD-1) % MOD << '\n';
	return 0;
}

Compilation message

boat.cpp: In function 'int32_t main()':
boat.cpp:24:8: warning: unused variable 'ans' [-Wunused-variable]
  int n,ans = 0;
        ^~~

Subtask #1

9.0 / 9.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	776 KB	Output is correct
2	Correct	4 ms	768 KB	Output is correct
3	Correct	5 ms	768 KB	Output is correct
4	Correct	7 ms	768 KB	Output is correct
5	Correct	5 ms	768 KB	Output is correct
6	Correct	4 ms	768 KB	Output is correct
7	Correct	5 ms	768 KB	Output is correct
8	Correct	4 ms	768 KB	Output is correct
9	Correct	4 ms	768 KB	Output is correct
10	Correct	5 ms	768 KB	Output is correct
11	Correct	6 ms	768 KB	Output is correct
12	Correct	5 ms	768 KB	Output is correct
13	Correct	4 ms	768 KB	Output is correct
14	Correct	5 ms	768 KB	Output is correct
15	Correct	4 ms	768 KB	Output is correct
16	Correct	3 ms	384 KB	Output is correct
17	Correct	3 ms	512 KB	Output is correct
18	Correct	3 ms	512 KB	Output is correct
19	Correct	4 ms	384 KB	Output is correct
20	Correct	3 ms	512 KB	Output is correct

Subtask #2

22.0 / 22.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	776 KB	Output is correct
2	Correct	4 ms	768 KB	Output is correct
3	Correct	5 ms	768 KB	Output is correct
4	Correct	7 ms	768 KB	Output is correct
5	Correct	5 ms	768 KB	Output is correct
6	Correct	4 ms	768 KB	Output is correct
7	Correct	5 ms	768 KB	Output is correct
8	Correct	4 ms	768 KB	Output is correct
9	Correct	4 ms	768 KB	Output is correct
10	Correct	5 ms	768 KB	Output is correct
11	Correct	6 ms	768 KB	Output is correct
12	Correct	5 ms	768 KB	Output is correct
13	Correct	4 ms	768 KB	Output is correct
14	Correct	5 ms	768 KB	Output is correct
15	Correct	4 ms	768 KB	Output is correct
16	Correct	3 ms	384 KB	Output is correct
17	Correct	3 ms	512 KB	Output is correct
18	Correct	3 ms	512 KB	Output is correct
19	Correct	4 ms	384 KB	Output is correct
20	Correct	3 ms	512 KB	Output is correct
21	Correct	575 ms	512 KB	Output is correct
22	Correct	547 ms	760 KB	Output is correct
23	Correct	501 ms	740 KB	Output is correct
24	Correct	567 ms	636 KB	Output is correct
25	Correct	561 ms	632 KB	Output is correct
26	Correct	542 ms	524 KB	Output is correct
27	Correct	544 ms	676 KB	Output is correct
28	Correct	518 ms	572 KB	Output is correct
29	Correct	566 ms	632 KB	Output is correct
30	Correct	754 ms	50388 KB	Output is correct
31	Correct	736 ms	50156 KB	Output is correct
32	Correct	692 ms	50172 KB	Output is correct
33	Correct	747 ms	50192 KB	Output is correct
34	Correct	709 ms	50028 KB	Output is correct
35	Correct	708 ms	50176 KB	Output is correct
36	Correct	717 ms	50296 KB	Output is correct
37	Correct	737 ms	50216 KB	Output is correct
38	Correct	718 ms	50284 KB	Output is correct

Subtask #3

0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Execution timed out	2045 ms	127184 KB	Time limit exceeded
2	Halted	0 ms	0 KB	-

Subtask #4

0 / 42.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	4 ms	776 KB	Output is correct
2	Correct	4 ms	768 KB	Output is correct
3	Correct	5 ms	768 KB	Output is correct
4	Correct	7 ms	768 KB	Output is correct
5	Correct	5 ms	768 KB	Output is correct
6	Correct	4 ms	768 KB	Output is correct
7	Correct	5 ms	768 KB	Output is correct
8	Correct	4 ms	768 KB	Output is correct
9	Correct	4 ms	768 KB	Output is correct
10	Correct	5 ms	768 KB	Output is correct
11	Correct	6 ms	768 KB	Output is correct
12	Correct	5 ms	768 KB	Output is correct
13	Correct	4 ms	768 KB	Output is correct
14	Correct	5 ms	768 KB	Output is correct
15	Correct	4 ms	768 KB	Output is correct
16	Correct	3 ms	384 KB	Output is correct
17	Correct	3 ms	512 KB	Output is correct
18	Correct	3 ms	512 KB	Output is correct
19	Correct	4 ms	384 KB	Output is correct
20	Correct	3 ms	512 KB	Output is correct
21	Correct	575 ms	512 KB	Output is correct
22	Correct	547 ms	760 KB	Output is correct
23	Correct	501 ms	740 KB	Output is correct
24	Correct	567 ms	636 KB	Output is correct
25	Correct	561 ms	632 KB	Output is correct
26	Correct	542 ms	524 KB	Output is correct
27	Correct	544 ms	676 KB	Output is correct
28	Correct	518 ms	572 KB	Output is correct
29	Correct	566 ms	632 KB	Output is correct
30	Correct	754 ms	50388 KB	Output is correct
31	Correct	736 ms	50156 KB	Output is correct
32	Correct	692 ms	50172 KB	Output is correct
33	Correct	747 ms	50192 KB	Output is correct
34	Correct	709 ms	50028 KB	Output is correct
35	Correct	708 ms	50176 KB	Output is correct
36	Correct	717 ms	50296 KB	Output is correct
37	Correct	737 ms	50216 KB	Output is correct
38	Correct	718 ms	50284 KB	Output is correct
39	Execution timed out	2045 ms	127184 KB	Time limit exceeded
40	Halted	0 ms	0 KB	-