Submission #68428

#	Time	Username	Problem	Language	Result	Execution time	Memory
68428		gusfring	Boat (APIO16_boat)	C++14	31 / 100	2052 ms	525312 KiB

boat

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 505, MOD = 1e9 + 7;
typedef long long ll;
typedef pair<int, int> pii;
#define a first
#define b second

int N, A[MAXN], B[MAXN], T[1000505], bit[1000505], res, sum;
vector<pii> vec;

void update(int pos, int val){
	while(pos <= sum){
		bit[pos] = (bit[pos] + val) % MOD;
		pos += (pos & (-pos));
	}
}

int query(int pos){
	int r = 0;
	while(pos){
		r = (r + bit[pos]) % MOD;
		pos -= (pos & (-pos));
	}
	return r;
}

ll solve(){
	int cnt = 0;
	for(int i=1; i<=N; ++i)
		for(int j=B[i]; j>=A[i]; --j) vec.push_back({j, ++cnt});
	sort(vec.begin(), vec.end());
	T[vec[0].b] = 1, cnt = 1;
	for(int i=1; i<vec.size(); ++i){
		if(vec[i].a != vec[i - 1].a) cnt++;
		T[vec[i].b] = cnt;
	}
	for(int i=1; i<=sum; ++i){
		int r = (query(T[i] - 1) + 1) % MOD;
		update(T[i], r);
		res = (res + r) % MOD;
	}
	return res;
}
		
int main(){
	scanf("%d", &N);
	for(int i=1; i<=N; ++i){
		scanf("%d %d", &A[i], &B[i]);
		sum += B[i] - A[i] + 1;
	}
	printf("%lld\n", solve());
	return 0;
}
		

Compilation message (stderr)

boat.cpp: In function 'll solve()':
boat.cpp:36:16: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=1; i<vec.size(); ++i){
               ~^~~~~~~~~~~
boat.cpp: In function 'int main()':
boat.cpp:49:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &N);
  ~~~~~^~~~~~~~~~
boat.cpp:51:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &A[i], &B[i]);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 9 / 9
• Subtask 2: 22 / 22
• Subtask 3: 0 / 27
• Subtask 4: 0 / 42