oj.uz

Submission #1105907

# Submission time Handle Problem Language Result Execution time Memory
1105907 2024-10-28T10:07:35 Z _rain_ Boat (APIO16_boat) C++14
31 / 100
 482 ms 524288 KB 
#include<bits/stdc++.h>
using namespace std;

typedef long long ll ;
#define name "main"

const int N=(int)1e6;
const int MOD=(int)1e9+7;
int add(int a,int b){
	return a+b>=MOD?a+b-MOD:a+b;
}
int mul(int a,int b){
	return (ll)a*b%MOD;
}
int power(int a,int b){
	int res=1;
	for (;b;b>>=1,a=mul(a,a))
		if (b&1) res=mul(res,a);
	return res;
}
int a[N+2],b[N+2],f[N+2],n;
vector<int>nen;
vector<int>loop[N+2];
#define lef(id) id*2
#define rig(id) id*2+1
int st[N*4+2];
void upd(int id,int l,int r,int pos,int val){
	if (l>pos||r<pos) return;
	if (l==r){
		st[id]=add(st[id],val);
	}
	else{
		int m=(l+r)>>1;
		upd(lef(id),l,m,pos,val);
		upd(rig(id),m+1,r,pos,val);
		st[id]=add(st[lef(id)],st[rig(id)]);
	}
	return;
}
int Get(int id,int l,int r,int u,int v){
	if (l>v||r<u) return 0;
	if (u<=l&&r<=v) return st[id];
	int m=(l+r)>>1;
	return add(Get(lef(id),l,m,u,v),Get(rig(id),m+1,r,u,v));
}

int32_t main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);

	cin>>n;
	for(int i=1;i<=n;++i){
		cin>>a[i]>>b[i];
		for(int j=a[i];j<=b[i];++j) nen.push_back(j);
	}
	sort(nen.begin(),nen.end());
	nen.resize(unique(nen.begin(),nen.end())-nen.begin());
	for(int i=1;i<=n;++i){
		a[i]=upper_bound(nen.begin(),nen.end(),a[i])-nen.begin();
		b[i]=upper_bound(nen.begin(),nen.end(),b[i])-nen.begin();
		for (int j=a[i];j<=b[i];++j) loop[j].push_back(i);
	}
	upd(1,0,n,0,1);
	for(int i=1;i<=nen.size();++i){
		for (int j=0;j<loop[i].size();++j){
			f[j]=Get(1,0,n,0,loop[i][j]-1);
		}
		for(int j=0;j<loop[i].size();++j) upd(1,0,n,loop[i][j],f[j]);
		// cout<<"NEN: "<<nen[i-1]<<'\n';
		// for(int j=0;j<loop[i].size();++j) cout<<f[j]<<' ';
		// cout<<'\n';
	}
	cout<<Get(1,0,n,1,n)<<'\n';
	exit(0);
}

Compilation message

boat.cpp: In function 'int32_t main()':
boat.cpp:64:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   64 |  for(int i=1;i<=nen.size();++i){
      |              ~^~~~~~~~~~~~
boat.cpp:65:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   65 |   for (int j=0;j<loop[i].size();++j){
      |                ~^~~~~~~~~~~~~~~
boat.cpp:68:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |   for(int j=0;j<loop[i].size();++j) upd(1,0,n,loop[i][j],f[j]);
      |               ~^~~~~~~~~~~~~~~

Subtask #1
9.0 / 9.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29008 KB Output is correct
2 Correct 6 ms 29008 KB Output is correct
3 Correct 6 ms 29236 KB Output is correct
4 Correct 6 ms 29008 KB Output is correct
5 Correct 6 ms 29008 KB Output is correct
6 Correct 7 ms 29008 KB Output is correct
7 Correct 7 ms 29008 KB Output is correct
8 Correct 5 ms 29008 KB Output is correct
9 Correct 5 ms 29008 KB Output is correct
10 Correct 6 ms 29024 KB Output is correct
11 Correct 6 ms 29008 KB Output is correct
12 Correct 6 ms 29008 KB Output is correct
13 Correct 6 ms 29008 KB Output is correct
14 Correct 5 ms 29200 KB Output is correct
15 Correct 6 ms 29200 KB Output is correct
16 Correct 6 ms 29008 KB Output is correct
17 Correct 5 ms 29008 KB Output is correct
18 Correct 6 ms 29200 KB Output is correct
19 Correct 7 ms 29176 KB Output is correct
20 Correct 5 ms 29008 KB Output is correct

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29008 KB Output is correct
2 Correct 6 ms 29008 KB Output is correct
3 Correct 6 ms 29236 KB Output is correct
4 Correct 6 ms 29008 KB Output is correct
5 Correct 6 ms 29008 KB Output is correct
6 Correct 7 ms 29008 KB Output is correct
7 Correct 7 ms 29008 KB Output is correct
8 Correct 5 ms 29008 KB Output is correct
9 Correct 5 ms 29008 KB Output is correct
10 Correct 6 ms 29024 KB Output is correct
11 Correct 6 ms 29008 KB Output is correct
12 Correct 6 ms 29008 KB Output is correct
13 Correct 6 ms 29008 KB Output is correct
14 Correct 5 ms 29200 KB Output is correct
15 Correct 6 ms 29200 KB Output is correct
16 Correct 6 ms 29008 KB Output is correct
17 Correct 5 ms 29008 KB Output is correct
18 Correct 6 ms 29200 KB Output is correct
19 Correct 7 ms 29176 KB Output is correct
20 Correct 5 ms 29008 KB Output is correct
21 Correct 121 ms 37816 KB Output is correct
22 Correct 114 ms 38076 KB Output is correct
23 Correct 113 ms 37572 KB Output is correct
24 Correct 123 ms 38048 KB Output is correct
25 Correct 122 ms 37796 KB Output is correct
26 Correct 133 ms 38340 KB Output is correct
27 Correct 123 ms 38556 KB Output is correct
28 Correct 121 ms 38352 KB Output is correct
29 Correct 130 ms 38592 KB Output is correct
30 Correct 153 ms 64192 KB Output is correct
31 Correct 163 ms 63644 KB Output is correct
32 Correct 151 ms 64184 KB Output is correct
33 Correct 150 ms 63416 KB Output is correct
34 Correct 160 ms 63672 KB Output is correct
35 Correct 151 ms 62168 KB Output is correct
36 Correct 156 ms 63160 KB Output is correct
37 Correct 170 ms 63672 KB Output is correct
38 Correct 174 ms 62648 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 482 ms 524288 KB Execution killed with signal 9
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 29008 KB Output is correct
2 Correct 6 ms 29008 KB Output is correct
3 Correct 6 ms 29236 KB Output is correct
4 Correct 6 ms 29008 KB Output is correct
5 Correct 6 ms 29008 KB Output is correct
6 Correct 7 ms 29008 KB Output is correct
7 Correct 7 ms 29008 KB Output is correct
8 Correct 5 ms 29008 KB Output is correct
9 Correct 5 ms 29008 KB Output is correct
10 Correct 6 ms 29024 KB Output is correct
11 Correct 6 ms 29008 KB Output is correct
12 Correct 6 ms 29008 KB Output is correct
13 Correct 6 ms 29008 KB Output is correct
14 Correct 5 ms 29200 KB Output is correct
15 Correct 6 ms 29200 KB Output is correct
16 Correct 6 ms 29008 KB Output is correct
17 Correct 5 ms 29008 KB Output is correct
18 Correct 6 ms 29200 KB Output is correct
19 Correct 7 ms 29176 KB Output is correct
20 Correct 5 ms 29008 KB Output is correct
21 Correct 121 ms 37816 KB Output is correct
22 Correct 114 ms 38076 KB Output is correct
23 Correct 113 ms 37572 KB Output is correct
24 Correct 123 ms 38048 KB Output is correct
25 Correct 122 ms 37796 KB Output is correct
26 Correct 133 ms 38340 KB Output is correct
27 Correct 123 ms 38556 KB Output is correct
28 Correct 121 ms 38352 KB Output is correct
29 Correct 130 ms 38592 KB Output is correct
30 Correct 153 ms 64192 KB Output is correct
31 Correct 163 ms 63644 KB Output is correct
32 Correct 151 ms 64184 KB Output is correct
33 Correct 150 ms 63416 KB Output is correct
34 Correct 160 ms 63672 KB Output is correct
35 Correct 151 ms 62168 KB Output is correct
36 Correct 156 ms 63160 KB Output is correct
37 Correct 170 ms 63672 KB Output is correct
38 Correct 174 ms 62648 KB Output is correct
39 Runtime error 482 ms 524288 KB Execution killed with signal 9
40 Halted 0 ms 0 KB -