Submission #887712

#	Time	Username	Problem	Language	Result	Execution time	Memory
887712		cpptowin	Fancy Fence (CEOI20_fancyfence)	C++17	100 / 100	36 ms	13272 KiB

fancyfence

#include<bits/stdc++.h>
#define fo(i,d,c) for(int i=d;i<=c;i++)
#define fod(i,c,d) for(int i=c;i>=d;i--)
#define maxn 1000010
#define N 1010
#define fi first
#define se second
#define pb emplace_back
#define en cout<<"\n";
#define int long long
#define inf 1000000000
#define pii pair<int,int>
#define vii vector<pii>
#define lb(x) x&-x
#define bit(i,j) ((i>>j)&1)
#define offbit(i,j) (i^(1<<j))
#define onbit(i,j) (i|(1<<j))
#define vi vector<int>
template <typename T1, typename T2> bool minimize(T1 &a, T2 b)
{
    if (a > b)
    {
        a = b;
        return true;
    }
    return false;
}
template <typename T1, typename T2> bool maximize(T1 &a, T2 b)
{
    if (a < b)
    {
        a = b;
        return true;
    }
    return false;
}
using namespace std;
const int mod = 1e9 + 7;
int n;
int h[maxn],w[maxn];
int inv[maxn];
int Pow(int a,int n)
{
    int ans = 1;
    for( ; n ; n >>= 1, a = ((a * a) % mod + mod) % mod) if(n & 1)
        {
            ans = ((ans * a) % mod + mod) % mod;
        }
    return ans;
}
int C(int n)
{
    return n % mod * (n - 1) % mod * inv[2] % mod ;
}
int T(int a,int b)
{
    return C(a + 1) * C(b + 1) % mod;
}
int ans;
int done[maxn];
struct DSU
{
    vi par,sz;
    DSU(int n) : par(n),sz(n) {};
    void make(int u)
    {
        par[u] = u;
        sz[u] = 1;
    }
    int find(int u)
    {
        return u == par[u] ? u : par[u] = find(par[u]);
    }
    void Union(int u,int v,int h)
    {
        u = find(u);
        v = find(v);
        if(u == v) return ;
        ans = (ans + T(h,w[u] + w[v]) - T(h,w[u]) - T(h,w[v])) % mod;
        ans = (ans + mod) % mod;
        if(sz[u] < sz[v]) swap(u,v);
        sz[u] += sz[v];
        par[v] = u;
        w[u] = (w[u] + w[v]) % mod;
    }
};
main()
{
#define name "TASK"
    if(fopen(name".inp","r"))
    {
        freopen(name".inp","r",stdin);
        freopen(name".out","w",stdout);
    }
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    inv[2] = Pow(2,mod - 2);
    cin >> n;
    fo(i,1,n) cin >> h[i];
    fo(i,1,n) cin >> w[i];
    DSU g(n + 5);
    fo(i,1,n) g.make(i);
    fo(i,1,n) ans = (ans + T(w[i],h[i])) % mod;
    vi v;
    fo(i,1,n) v.pb(i);
    sort(v.begin(),v.end(),[](int a,int b)
         {
             return h[a] > h[b];
         });
    for(int i : v)
    {
        if(h[i] <= h[i + 1] and done[i + 1])
        {
            g.Union(i,i + 1,h[i]);
        }
        if(h[i] <= h[i - 1] and done[i - 1])
        {
            g.Union(i,i - 1,h[i]);
        }
        done[i] = 1;
    }
    cout << ans;
}

Compilation message (stderr)

fancyfence.cpp:87:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   87 | main()
      | ^~~~
fancyfence.cpp: In function 'int main()':
fancyfence.cpp:92:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   92 |         freopen(name".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
fancyfence.cpp:93:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   93 |         freopen(name".out","w",stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 0 / 0
• Subtask 2: 12 / 12
• Subtask 3: 13 / 13
• Subtask 4: 15 / 15
• Subtask 5: 15 / 15
• Subtask 6: 18 / 18
• Subtask 7: 27 / 27