oj.uz

Submission #298995

# Submission time Handle Problem Language Result Execution time Memory
298995 2020-09-14T11:54:13 Z square1001 Fancy Fence (CEOI20_fancyfence) C++14
43 / 100
 47 ms 4216 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;
		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.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct

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
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 23 ms 2304 KB Output is correct
4 Correct 43 ms 3832 KB Output is correct
5 Correct 47 ms 4216 KB Output is correct
6 Correct 41 ms 3448 KB Output is correct

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 4 ms 640 KB Output is correct
3 Correct 19 ms 2060 KB Output is correct
4 Correct 38 ms 3836 KB Output is correct
5 Correct 40 ms 3960 KB Output is correct
6 Correct 1 ms 384 KB Output is correct

Subtask #5
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 4 ms 640 KB Output is correct
4 Correct 22 ms 2048 KB Output is correct
5 Correct 37 ms 3840 KB Output is correct
6 Correct 41 ms 3960 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 4 ms 640 KB Output is correct
9 Correct 19 ms 2176 KB Output is correct
10 Correct 35 ms 3712 KB Output is correct
11 Correct 37 ms 3840 KB Output is correct
12 Correct 1 ms 384 KB Output is correct

Subtask #6
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Runtime error 1 ms 512 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 512 KB Output is correct
5 Runtime error 1 ms 512 KB Execution killed with signal 11
6 Halted 0 ms 0 KB -