oj.uz

Submission #572664

# Submission time Handle Problem Language Result Execution time Memory
572664 2022-06-05T00:23:09 Z jiahng Fancy Fence (CEOI20_fancyfence) C++14
12 / 100
 2 ms 388 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
//~ #define ll int
#define ll int
typedef pair<int32_t, int32_t> pi;
typedef vector <int> vi;
typedef vector <pi> vpi;
typedef pair<pi, ll> pii;
typedef set <ll> si;
typedef long double ld;
#define f first
#define s second
#define mp make_pair
#define FOR(i,s,e) for(int i=s;i<=int(e);++i)
#define DEC(i,s,e) for(int i=s;i>=int(e);--i)
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define lbd(x, y) lower_bound(all(x), y)
#define ubd(x, y) upper_bound(all(x), y)
#define aFOR(i,x) for (auto i: x)
#define mem(x,i) memset(x,i,sizeof x)
#define fast ios_base::sync_with_stdio(false),cin.tie(0),cout.tie(0)
#define maxn 200001
#define INF 1e9
#define MOD 1000000007
typedef pair <vi, int> pvi;
typedef pair <int,pi> ipi;
typedef vector <pii> vpii;

int N,H[maxn],W[maxn],ss[maxn],ss2[maxn];
int32_t main(){
    fast;
    cin >> N;
    FOR(i,1,N) cin >> H[i];
    FOR(i,1,N) cin >> W[i];
    FOR(i,1,N){
		ss[i] = (ss[i-1] + W[i]) % MOD;
		ss2[i] = (ss2[i-1] + (W[i] * W[i]) % MOD) % MOD;
	}
    
    set <int> st;
    vi v(N); iota(all(v), 1);
    sort(all(v), [](int i,int j){
		return H[i] < H[j];
	});
	int ans = 0;
	st.insert(N+1); st.insert(0);
	aFOR(i,v){
		int l = *(--st.lower_bound(i)) + 1;
		int r = *st.upper_bound(i) - 1;
		
		int res = 0;
		(res += ((ss[r] - ss[l-1]) * (ss[r] - ss[l-1])) % MOD) %= MOD;
		(res -= (ss2[r] - ss2[l-1]) % MOD) %= MOD;
		
		(res -= ((ss[r] - ss[i]) * (ss[r] - ss[i])) % MOD) %= MOD;
		(res += (ss2[r] - ss2[i]) % MOD) %= MOD;
		
		(res -= ((ss[i-1] - ss[l-1]) * (ss[i-1] - ss[l-1])) % MOD) %= MOD;
		(res += (ss2[i-1] - ss2[l-1]) % MOD) %= MOD;
		res /= 2;
		//~ (res -= (W[i] * W[i]) % MOD) %= MOD;
		int hc2 = (H[i] * (H[i] + 1) / 2) % MOD;
		(ans += (res * hc2) % MOD) %= MOD;
		//~ cout << ans << '\n';
		st.insert(i);
	}    
	
	FOR(i,1,N){
		(ans += ((((W[i] * (W[i]+1)) / 2) % MOD)
			* (((H[i] * (H[i]+1)) / 2) % MOD)) % MOD) %= MOD;
	}
	if (ans < 0) ans += MOD;
	cout << ans;
}

Subtask #1
0.0 / 0.0

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

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 0 ms 328 KB Output is correct
5 Correct 1 ms 340 KB Output is correct

Subtask #3
0 / 13.0

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

Subtask #4
0 / 15.0

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

Subtask #5
0 / 15.0

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

Subtask #6
0 / 18.0

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

Subtask #7
0 / 27.0

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