oj.uz

Submission #881429

# Submission time Handle Problem Language Result Execution time Memory
881429 2023-12-01T08:46:05 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;
vector<int> h;
vector<int> ps;
int tmp = 0;
void sl(int 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]));
    }
}
int32_t main() 
{
    tof_io;
    int n;
    cin >> n;

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

    for (int i = 1; i <= n; i++) 
    {
        sl(i);
        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 'void sl(long long int)':
fancyfence.cpp:37:13: warning: unused variable 'x' [-Wunused-variable]
   37 |         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 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 13.0

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