oj.uz

Submission #623666

# Submission time Handle Problem Language Result Execution time Memory
623666 2022-08-06T09:08:42 Z Vladth11 Fancy Fence (CEOI20_fancyfence) C++14
15 / 100
 26 ms 5460 KB 
#include <bits/stdc++.h>
#define debug(x) cerr << #x << " " << x << "\n"
#define debugs(x) cerr << #x << " " << x << " "

using namespace std;
typedef long long ll;
typedef pair <ll, ll> pii;
typedef pair <long double, pii> muchie;

const ll NMAX = 100001;
const ll VMAX = 101;
const ll INF = (1LL << 60);
const ll MOD = 1000000007;
const ll BLOCK = 447;
const ll base = 117;
const ll nr_of_bits = 18;
const ll inv2 = 500000004;

pii stiva[NMAX];
ll vf;
ll scor = 0;
ll h[NMAX];
ll w[NMAX];

ll lgput(ll n, ll p){
    ll rez = 1;
    while(p){
        if(p % 2){
            rez = (1LL * rez * n) % MOD;
        }
        n = (1LL * n * n) % MOD;
        p /= 2;
    }
    return rez;
}

ll gauss(ll x){
    return 1LL * (1LL * x * (x + 1)) % MOD * inv2 % MOD;
}

ll cate(ll h, ll w){
    return (1LL * gauss(h) * gauss(w)) % MOD;
}

ll combined(ll h, ll w1, ll w2){
    return (1LL * (1LL * gauss(h) * w1) % MOD * w2) % MOD;
}

void add(ll &x, ll val){
    x += val;
    if(x >= MOD){
        x -= MOD;
    }
    if(x < 0){
        x += MOD;
    }
}

int main() {
    //ifstream cin(".in");
    //ofstream cout(".out");
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    ll n, i;
    ll total = 0;
    cin >> n;
    for(i = 1; i <= n; i++) cin >> h[i];
    for(i = 1; i <= n; i++) cin >> w[i];
    for(i = 1; i <= n; i++){
        add(total, cate(h[i], w[i]));
        ll avem = w[i];
        while(vf && stiva[vf].first >= h[i]){
            add(total, combined(h[i], stiva[vf].second, w[i]));
            add(avem, stiva[vf].second);
            vf--;
        }
        stiva[++vf] = {h[i], avem};
    }
    vf = 0;
    for(i = n; i >= 1; i--){
        ll avem = w[i];
        while(vf && stiva[vf].first > h[i]){
            add(total, combined(h[i], stiva[vf].second, w[i]));
            add(avem, stiva[vf].second);
            vf--;
        }
        stiva[++vf] = {h[i], avem};
    }
    //debug(total);
    cout << total;
    return 0;
}

Subtask #1
0.0 / 0.0

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

Subtask #2
0 / 12.0

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

Subtask #3
0 / 13.0

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

Subtask #4
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 3 ms 852 KB Output is correct
3 Correct 12 ms 2772 KB Output is correct
4 Correct 24 ms 5328 KB Output is correct
5 Correct 26 ms 5460 KB Output is correct
6 Correct 1 ms 336 KB Output is correct

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 3 ms 852 KB Output is correct
4 Correct 12 ms 2772 KB Output is correct
5 Correct 23 ms 5364 KB Output is correct
6 Correct 26 ms 5448 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 4 ms 852 KB Output is correct
9 Correct 13 ms 2524 KB Output is correct
10 Incorrect 25 ms 5236 KB Output isn't correct
11 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 328 KB Output is correct
2 Incorrect 1 ms 340 KB Output isn't correct
3 Halted 0 ms 0 KB -