oj.uz

Submission #298994

# Submission time Handle Problem Language Result Execution time Memory
298994 2020-09-14T11:53:43 Z square1001 Fancy Fence (CEOI20_fancyfence) C++14
0 / 100
 5 ms 512 KB 
#include <set>
#include <vector>
#include <iostream>
#include <algorithm>
using namespace std;
const int mod = 1000000007;
int main() {
	cin.tie(0);
	ios_base::sync_with_stdio(false);
	int N;
	cin >> N;
	vector<int> H(N), W(N);
	for(int i = 0; i < N; ++i) cin >> H[i];
	for(int i = 0; i < N; ++i) cin >> W[i];
	vector<int> WS(N);
	for(int i = 0; i < N; ++i) {
		WS[i + 1] = WS[i] + W[i];
		if(WS[i + 1] >= mod) WS[i + 1] -= mod;
	}
	vector<int> perm(N);
	for(int i = 0; i < N; ++i) {
		perm[i] = i;
	}
	sort(perm.begin(), perm.end(), [&](int i, int j) { return H[i] > H[j]; });
	set<pair<int, int> > s;
	long long current = 0;
	int ans = 0;
	for(int i = 0; i < perm.size(); ++i) {
		int id = perm[i];
		current = (current + 1LL * W[id] * (W[id] + 1)) % mod;
		set<pair<int, int> >::iterator it = s.lower_bound(make_pair(id, -1));
		int cl = id, cr = id + 1;
		if(it != s.end()) {
			if(it->first == cr) {
				// connect!
				current -= 1LL * (WS[cr] - WS[cl] + mod) * (WS[cr] - WS[cl] + mod + 1) % mod;
				current -= 1LL * (WS[it->second] - WS[it->first] + mod) * (WS[it->second] - WS[it->first] + mod + 1) % mod;
				cr = it->second;
				current += 1LL * (WS[cr] - WS[cl] + mod) * (WS[cr] - WS[cl] + mod + 1) % mod;
				it = s.erase(it);
			}
		}
		if(it != s.begin()) {
			--it;
			if(it->second == cl) {
				// connect!
				current -= 1LL * (WS[cr] - WS[cl] + mod) * (WS[cr] - WS[cl] + mod + 1) % mod;
				current -= 1LL * (WS[it->second] - WS[it->first] + mod) * (WS[it->second] - WS[it->first] + mod + 1) % mod;
				cl = it->first;
				current += 1LL * (WS[cr] - WS[cl] + mod) * (WS[cr] - WS[cl] + mod + 1) % mod;
				it = s.erase(it);
			}
		}
		s.insert(make_pair(cl, cr));
		while(current < 0) current += mod;
		while(current >= mod) current -= mod;
		cout << perm[i] << ' ' << current << endl;
		int hr = H[perm[i]], hl = (i + 1 != N ? H[perm[i + 1]] : 0);
		int hc = (1LL * hr * (hr + 1) / 2 - 1LL * hl * (hl + 1) / 2) % mod;
		int sub = 1LL * current * hc % mod;
		ans = (ans + sub) % mod;
	}
	ans = 1LL * ans * (mod / 2 + 1) % mod;
	cout << ans << endl;
	return 0;
}

Compilation message

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:28:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |  for(int i = 0; i < perm.size(); ++i) {
      |                 ~~^~~~~~~~~~~~~

Subtask #1
0 / 0.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 12.0

# Verdict Execution time Memory Grader output
1 Runtime error 1 ms 512 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 5 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 388 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 384 KB Output isn't correct
2 Halted 0 ms 0 KB -