oj.uz

답안 #261940

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
261940 2020-08-12T08:10:58 Z define Boat (APIO16_boat) C++11
0 / 100
 1 ms 384 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;



struct BIT{
	int N;
	vector<int>bit;
	void add(int x,int y){
		while(x<=N){
			(bit[x]+=y)%=mod;x+=x&-x;
		}
	}
	int sum(int x){
		int res=0;
		while(x>0){
			(res+=bit[x])%=mod;x-=x&-x;
		}
		return res;
	}
	BIT(int x):N(x),bit(x+1){}
};

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];
		x.push_back(A[i]);
		x.push_back(B[i]);
	}
	sort(all(x));x.erase(unique(all(x)),x.end());
	BIT bit(len(x));
	bit.add(1,1);
	rep(i,N){
		B[i]=lower_bound(all(x),B[i])-x.begin()+1;
		A[i]=lower_bound(all(x),A[i])-x.begin()+1;
		for(int j=B[i];j>=A[i];j--){
			int k=bit.sum(j-1)*(x[j-1]-x[j-2])%mod;
			bit.add(j,k);
		}
	}
	cout<<(bit.sum(len(x))-1+mod)%mod<<endl;
}

Subtask #1
0 / 9.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 42.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -