제출 #1334668

#제출 시각아이디문제언어결과실행 시간메모리
1334668tvdanFancy Fence (CEOI20_fancyfence)C++20
28 / 100
15 ms1988 KiB
//ojou kawayo no.1
#include <bits/stdc++.h>
using namespace std;
#define tsk "FancyFence"
#define pb push_back
#define pf push_front
#define fi first
#define se second
#define Ningen_sama signed
#define tachi main()
#define __builtin_popcount __builtin_popcountll
#define el cout<<'\n'
#define all(a) a.begin(),a.end()
#define invAll(a) a.rbegin(),a.rend()
#define sz(a) ((int)a.size())
#define BIT(x, k) (1ll&((x) >> (k)))
#define mem(a,x) memset(a,x,sizeof(a))
#define debug(x) cout << #x << " = " << x << '\n'
#define execute cerr << "Time elapsed: " << (1.0 * clock() / CLOCKS_PER_SEC) << "s"
#define FOR(i, l, r) for(int i = (l); i <= (r); ++i)
#define FORD(i, l, r) for(int i = (l); i >= (r); --i)
#define REP(i, n) for(int i = 0; i < (n); ++i)
#define int long long

template<class T> bool maximize(T& u, T v){if(u >= v) return false;return u = v, true;}
template<class T> bool minimize(T& u, T v){if(u <= v) return false;return u = v, true;}

using pii = pair<int, int>;
using ll = long long;
using vi = vector<int>;
using vpii = vector<pair<int, int>>;

#define inf32 0x3f3f3f3f
#define inf64 0x3f3f3f3f3f3f3f3f
const int maxn = 1e6+5;
const int N = 5e3 + 5;
const int base = 31;
const ll mod = 1e9 + 7;
const ll need = 67108863;
const int vc = 2e9 + 1;
const ll INF18 = 4557430888798830399;
const ll LOG = 20;
const double eps = 1e-9;
const int BLOCK = 447;
const int dx[4] = {1, 0, -1, 0};
const int dy[4] = {0, -1, 0, 1};

mt19937_64 rd(chrono::steady_clock::now().time_since_epoch().count());
#define rand rd
inline long long Rand(long long L, long long R) {
    if(L>R) return 0;
    return L + rd() % (R - L + 1);
}

inline ll add(ll x, ll y){x+=y;if(x>=mod) x-=mod;if(x<0) x+=mod;return x;}
inline ll mult(ll x, ll y){return 1LL * x * y % mod;}

ll calPow(ll a, ll b){
    ll s = 1;
    while(b){
        if(b & 1) s = s * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return s;
}

int n;
int w[maxn], h[maxn];
int r, c;
bool checkSub4 = true, checkSub3 = true;

inline void init(){

}

inline void input(){
    cin >> n;
    FOR(i, 1, n){
        cin >> h[i];
        if(i != 1 && h[i] != h[i - 1]) checkSub4 = false;
        if(h[i] > 2) checkSub3 = false;
    }
    FOR(i, 1, n) cin >> w[i], c += w[i];
}

namespace sub4{
    inline void solve(){
        r = h[1];

        ll res = (r * (r + 1) % mod * 500000004 % mod) * ((c % mod) * ((c + 1) % mod) % mod * 500000004 % mod) % mod;

        cout << res;
    }
}

namespace sub3{
    inline void solve(){
        r = h[1];

        ll res = ((c % mod) * ((c + 1) % mod) % mod * 500000004 % mod);
//        cout << res; el;

        int cnt2 = 0;
        FOR(i, 1, n){
            if(h[i] == 2){
                cnt2 += w[i];
            }
            else if(cnt2 != 0){
                res = add(res, cnt2 % mod);
                res = add(res, (cnt2 % mod) * ((cnt2 + 1) % mod) % mod * 500000004 % mod);
                res = add(res, (cnt2 % mod) * ((cnt2 - 1) % mod) % mod * 500000004 % mod);
                cnt2 = 0;
            }
        }

        res = add(res, cnt2 % mod);
        res = add(res, (cnt2 % mod) * ((cnt2 + 1) % mod) % mod * 500000004 % mod);
        res = add(res, (cnt2 % mod) * ((cnt2 - 1) % mod) % mod * 500000004 % mod);
        cnt2 = 0;

        cout << res;
    }
}

namespace sub6{
    inline void solve(){
        stack<int> st;
        ll res = ((c % mod) * ((c + 1) % mod) % mod * 500000004 % mod);
        st.push(1);
        c = 0;
        FOR(i, 1, n){
            if(h[i] == st.top()) continue;
            if(h[i] > st.top()){
                r = h[i] - st.top();
                c = w[i];
                FOR(j, i + 1, n){
                    if(h[j] < h[i]){
                        break;
                    }
                    else c += w[j];
                }
                
                res = add(res, (r * (r + 1) % mod * 500000004 % mod) * ((c % mod) * ((c + 1) % mod) % mod * 500000004 % mod) % mod);
                st.push(h[i]);
            }
            if(h[i] < st.top()){
                while(h[i] < st.top()) st.pop();
                if(h[i] > st.top()){
                r = h[i] - st.top();
                c = w[i];
                FOR(j, i + 1, n){
                    if(h[j] < h[i]){
                        break;
                    }
                    else c += w[j];
                }
                
                res = add(res, (r * (r + 1) % mod * 500000004 % mod) * ((c % mod) * ((c + 1) % mod) % mod * 500000004 % mod) % mod);
                st.push(h[i]);
                }
            }
        }
        
        cout << res;
    }
}

Ningen_sama tachi{
    //konnakiri~~
    if(fopen(tsk".inp","r")){
        freopen(tsk".inp","r",stdin);
        freopen(tsk".out","w",stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);

    input();

    if(checkSub4) sub4::solve();
    else if(checkSub3) sub3::solve();
    else sub6::solve();
}
//otsunakiri~~

컴파일 시 표준 에러 (stderr) 메시지

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:172:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  172 |         freopen(tsk".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~
fancyfence.cpp:173:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  173 |         freopen(tsk".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...