oj.uz

Submission #881432

# Submission time Handle Problem Language Result Execution time Memory
881432 2023-12-01T08:47:29 Z Danet Fancy Fence (CEOI20_fancyfence) C++14
0 / 100
 1 ms 348 KB 
#include<bits/stdc++.h>
using namespace std;

#pragma GCC optimize("O3")

#define tof_io  ios_base::sync_with_stdio(false);cin.tie(0) , cout.tie(0);
#define double  long double
#define int     long long
#define pb      push_back
#define all(x)  x.begin(),x.end()
#define endl    '\n'

const int mod = 1e9+7; //998244353
const long long inf = 1e18;
const int N = 1e3 + 23;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, 1, 0, -1};
const int modgg = (mod + 1)/ 2;
int modplus(int x) {if (x >= mod) {x -= mod;} else if (x < 0) {x += mod;}return x;} 
int nc2(int x){x = x * (x+1);return x;}
vector<pair<int, int>> s;
int res = 0;
int ans = 0;

int tmp = 0;
int32_t main() 
{
    tof_io;
    int n;
    cin >> n;
    vector<int> h(n+1);
    vector<int> ps(n+1);
    for (int i = 1; i <= n; i++) 
    {
        cin >> h[i];
    }
    for (int i = 1; i <= n; i++) 
    {
        cin >> ps[i];
        ps[i] = ps[i] + ps[i-1];
    }
    
    s.pb(make_pair(0ll,0ll));

    for (int i = 1; i <= n; i++) 
    {
        while (s.back().first >= h[i]) 
        {
            tmp = (s.back().second - s[s.size() - 2ll].second) % mod;
            res = modplus(res - tmp * ( nc2(s.back().first) / 2 % mod) % mod);
            s.pop_back();
        }
        if (s.back().second != ps[i-1]) 
        {
            int x = (ps[i - 1] - s.back().second) % mod;
            res = modplus(res + tmp * (nc2(h[i]) / 2 % mod) % mod);
            s.pb(make_pair(h[i], ps[i - 1]));
        }
        int x = (ps[i] - ps[i - 1]) % mod;
        ans = modplus(ans + res % mod * x % mod);
        ans = modplus( ans + (nc2(x) % mod * modgg % mod) * (nc2(h[i]) * modgg % mod) % mod );
        res = modplus(res + (nc2(h[i]) / 2 % mod) * x % mod);
        s.pb(make_pair(h[i], ps[i]));
    }
    
    cout << ans;
}

Compilation message

fancyfence.cpp: In function 'int32_t main()':
fancyfence.cpp:55:17: warning: unused variable 'x' [-Wunused-variable]
   55 |             int x = (ps[i - 1] - s.back().second) % mod;
      |                 ^

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Incorrect 0 ms 348 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 344 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 348 KB Output is correct
2 Incorrect 0 ms 348 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 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

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

Subtask #6
0 / 18.0

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

Subtask #7
0 / 27.0

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