Submission #572666

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
572666	2022-06-05T00:32:52 Z	jiahng	Fancy Fence (CEOI20_fancyfence)	C++14	100 / 100	85 ms	10972 KB

fancyfence

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
//~ #define ll int
#define int ll
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[i]) * (ss[i-1] - ss[l-1])) % MOD) %= MOD;
		(res += (W[i] * (ss[r] - ss[l-1] - W[i])) % MOD) %= MOD;
		
		//~ (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	0 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct

Subtask #2
12.0 / 12.0

#	Verdict	Memory	Grader output
1	Correct	340 KB	Output is correct
2	Correct	340 KB	Output is correct
3	Correct	340 KB	Output is correct
4	Correct	340 KB	Output is correct
5	Correct	340 KB	Output is correct

Subtask #3
13.0 / 13.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	23 ms	5148 KB	Output is correct
4	Correct	48 ms	10036 KB	Output is correct
5	Correct	52 ms	10004 KB	Output is correct
6	Correct	46 ms	10068 KB	Output is correct

Subtask #4
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	340 KB	Output is correct
2	Correct	5 ms	1364 KB	Output is correct
3	Correct	24 ms	5600 KB	Output is correct
4	Correct	49 ms	10812 KB	Output is correct
5	Correct	51 ms	10972 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct

Subtask #5
15.0 / 15.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	5 ms	1344 KB	Output is correct
4	Correct	24 ms	5536 KB	Output is correct
5	Correct	50 ms	10872 KB	Output is correct
6	Correct	50 ms	10892 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	5 ms	1368 KB	Output is correct
9	Correct	27 ms	5524 KB	Output is correct
10	Correct	52 ms	10740 KB	Output is correct
11	Correct	59 ms	10784 KB	Output is correct
12	Correct	0 ms	340 KB	Output is correct

Subtask #6
18.0 / 18.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	340 KB	Output is correct
5	Correct	0 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	0 ms	332 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	1 ms	340 KB	Output is correct
12	Correct	1 ms	340 KB	Output is correct
13	Correct	1 ms	340 KB	Output is correct
14	Correct	1 ms	340 KB	Output is correct
15	Correct	1 ms	344 KB	Output is correct
16	Correct	1 ms	340 KB	Output is correct

Subtask #7
27.0 / 27.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	340 KB	Output is correct
2	Correct	1 ms	340 KB	Output is correct
3	Correct	0 ms	340 KB	Output is correct
4	Correct	1 ms	344 KB	Output is correct
5	Correct	1 ms	340 KB	Output is correct
6	Correct	1 ms	340 KB	Output is correct
7	Correct	1 ms	340 KB	Output is correct
8	Correct	1 ms	340 KB	Output is correct
9	Correct	1 ms	340 KB	Output is correct
10	Correct	1 ms	340 KB	Output is correct
11	Correct	23 ms	5168 KB	Output is correct
12	Correct	46 ms	10100 KB	Output is correct
13	Correct	48 ms	10064 KB	Output is correct
14	Correct	46 ms	10032 KB	Output is correct
15	Correct	1 ms	340 KB	Output is correct
16	Correct	5 ms	1364 KB	Output is correct
17	Correct	32 ms	5520 KB	Output is correct
18	Correct	48 ms	10828 KB	Output is correct
19	Correct	51 ms	10928 KB	Output is correct
20	Correct	1 ms	340 KB	Output is correct
21	Correct	5 ms	1364 KB	Output is correct
22	Correct	26 ms	5532 KB	Output is correct
23	Correct	52 ms	10752 KB	Output is correct
24	Correct	62 ms	10828 KB	Output is correct
25	Correct	1 ms	340 KB	Output is correct
26	Correct	1 ms	340 KB	Output is correct
27	Correct	1 ms	344 KB	Output is correct
28	Correct	1 ms	340 KB	Output is correct
29	Correct	1 ms	356 KB	Output is correct
30	Correct	7 ms	1364 KB	Output is correct
31	Correct	6 ms	1344 KB	Output is correct
32	Correct	31 ms	5488 KB	Output is correct
33	Correct	36 ms	5568 KB	Output is correct
34	Correct	74 ms	10584 KB	Output is correct
35	Correct	71 ms	10640 KB	Output is correct
36	Correct	80 ms	10828 KB	Output is correct
37	Correct	76 ms	10888 KB	Output is correct
38	Correct	0 ms	340 KB	Output is correct
39	Correct	85 ms	10764 KB	Output is correct
40	Correct	73 ms	10856 KB	Output is correct
41	Correct	56 ms	10784 KB	Output is correct
42	Correct	60 ms	10768 KB	Output is correct

Submission #572666

Compilation message

Subtask #1 0.0 / 0.0

Subtask #2 12.0 / 12.0

Subtask #3 13.0 / 13.0

Subtask #4 15.0 / 15.0

Subtask #5 15.0 / 15.0

Subtask #6 18.0 / 18.0

Subtask #7 27.0 / 27.0

Subtask #1
0.0 / 0.0

Subtask #2
12.0 / 12.0

Subtask #3
13.0 / 13.0

Subtask #4
15.0 / 15.0

Subtask #5
15.0 / 15.0

Subtask #6
18.0 / 18.0

Subtask #7
27.0 / 27.0