oj.uz

Submission #261988

# Submission time Handle Problem Language Result Execution time Memory
261988 2020-08-12T08:53:04 Z define Boat (APIO16_boat) C++17
31 / 100
 712 ms 524292 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,n) for(int i=0;i<n;i++)
#define REP(i,n) for(int i=1;i<n;i++)
#define rev(i,n) for(int i=n-1;i>=0;i--)
#define all(v) v.begin(),v.end()
#define P pair<int,int>
#define len(s) (int)s.size()

template<class T> inline bool chmin(T &a, T b){
	if(a>b){a=b;return true;}
	return false;
}
template<class T> inline bool chmax(T &a, T b){
	if(a<b){a=b;return true;}
	return false;
}
constexpr int mod = 1e9+7;
constexpr long long inf = 3e18;

template<typename Monoid,typename OperatorMonoid,typename F,typename G,typename H>
struct Segtree{
	int size=1;
	vector<Monoid>dat;
	vector<OperatorMonoid>lazy;
	const F f;
	const G g;
	const H h;
	Monoid M;
	OperatorMonoid OM;
	void set(int a,Monoid x){
		dat[a+size-1]=x;
	}
	void init(){
		for(int i=size-2;i>=0;i--){
			dat[i]=f(dat[i*2+1],dat[i*2+2]);
		}
	}
	void eval(int k,int l,int r){
		if(lazy[k]!=OM){
			dat[k]=g(dat[k],lazy[k],(r-l));
			if(r-l>1){
				lazy[2*k+1]=h(lazy[2*k+1],lazy[k]);
				lazy[2*k+2]=h(lazy[2*k+2],lazy[k]);
			}
			lazy[k]=OM;
		}
	}
	void update(int a,int b,OperatorMonoid M,int k=0,int l=0,int r=-1){
		if(r==-1)r=size;
		eval(k,l,r);
		if(r<=a||b<=l)return;
		if(a<=l&&r<=b){
			lazy[k]=h(lazy[k],M);
			eval(k,l,r);
			return;
		}
		update(a,b,M,k*2+1,l,(l+r)/2);
		update(a,b,M,k*2+2,(l+r)/2,r);
		dat[k]=f(dat[k*2+1],dat[k*2+2]);
	}
	Monoid query(int a,int b,int k=0,int l=0,int r=-1){
		if(r==-1)r=size;
		eval(k,l,r);
		if(r<=a||b<=l)return M;
		if(a<=l&&r<=b)return dat[k];
		Monoid lv=query(a,b,k*2+1,l,(l+r)/2);
		Monoid rv=query(a,b,k*2+2,(l+r)/2,r);
		return f(lv,rv);
	}
	Segtree(int x,F f,G g,H h,Monoid M,OperatorMonoid OM)
	:f(f),g(g),h(h),M(M),OM(OM){
		while(size<x)size*=2;
		dat.resize(size*2-1,M);
		lazy.resize(size*2-1,OM);
	}
};

int N,A[505],B[505];
vector<int>x={0};
signed main(){
	cin.tie(0);ios::sync_with_stdio(false);
	cin>>N;
	rep(i,N){
		cin>>A[i]>>B[i];
		for(int j=A[i];j<=B[i]+1;j++)x.push_back(j);
		
		/*x.push_back(A[i]);
		x.push_back(B[i]+1);
		*/
	}
	sort(all(x));x.erase(unique(all(x)),x.end());
	auto f=[](int a,int b){return (a+b)%mod;};
	auto g=[](int a,int b,int sz){return (a+b)%mod;};
	auto h=[](int a,int b){return (a+b)%mod;};
	Segtree<int,int,decltype(f),decltype(g),decltype(h)>segtree(len(x),f,g,h,0,0);
	segtree.set(0,1);segtree.init();
	rep(i,N){
		int l=lower_bound(all(x),A[i])-x.begin();
		int r=upper_bound(all(x),B[i])-x.begin();
		for(int j=r-1;j>=l;j--){
			int k=segtree.query(0,j)*(x[j+1]-x[j])%mod;
			segtree.update(j,j+1,k);
		}
	}
	cout<<(segtree.query(0,segtree.size)-1+mod)%mod<<endl;
}

Subtask #1
9.0 / 9.0

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

Subtask #2
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 380 ms 8688 KB Output is correct
22 Correct 415 ms 8688 KB Output is correct
23 Correct 355 ms 8688 KB Output is correct
24 Correct 396 ms 8688 KB Output is correct
25 Correct 426 ms 8688 KB Output is correct
26 Correct 394 ms 8688 KB Output is correct
27 Correct 390 ms 8816 KB Output is correct
28 Correct 378 ms 8688 KB Output is correct
29 Correct 412 ms 8688 KB Output is correct
30 Correct 649 ms 41152 KB Output is correct
31 Correct 674 ms 41044 KB Output is correct
32 Correct 712 ms 41156 KB Output is correct
33 Correct 624 ms 41044 KB Output is correct
34 Correct 648 ms 41024 KB Output is correct
35 Correct 614 ms 40660 KB Output is correct
36 Correct 653 ms 40916 KB Output is correct
37 Correct 652 ms 41048 KB Output is correct
38 Correct 636 ms 40788 KB Output is correct

Subtask #3
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 591 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 2 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 1 ms 384 KB Output is correct
6 Correct 2 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 2 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 2 ms 384 KB Output is correct
21 Correct 380 ms 8688 KB Output is correct
22 Correct 415 ms 8688 KB Output is correct
23 Correct 355 ms 8688 KB Output is correct
24 Correct 396 ms 8688 KB Output is correct
25 Correct 426 ms 8688 KB Output is correct
26 Correct 394 ms 8688 KB Output is correct
27 Correct 390 ms 8816 KB Output is correct
28 Correct 378 ms 8688 KB Output is correct
29 Correct 412 ms 8688 KB Output is correct
30 Correct 649 ms 41152 KB Output is correct
31 Correct 674 ms 41044 KB Output is correct
32 Correct 712 ms 41156 KB Output is correct
33 Correct 624 ms 41044 KB Output is correct
34 Correct 648 ms 41024 KB Output is correct
35 Correct 614 ms 40660 KB Output is correct
36 Correct 653 ms 40916 KB Output is correct
37 Correct 652 ms 41048 KB Output is correct
38 Correct 636 ms 40788 KB Output is correct
39 Runtime error 591 ms 524292 KB Execution killed with signal 9 (could be triggered by violating memory limits)
40 Halted 0 ms 0 KB -