oj.uz

Submission #373466

# Submission time Handle Problem Language Result Execution time Memory
373466 2021-03-04T18:00:03 Z jenkinsser Fancy Fence (CEOI20_fancyfence) C++17
30 / 100
 191 ms 262148 KB 
#include <bits/stdc++.h>
#define FOR(ii,aa,bb) for(int ii=aa;ii<bb;ii++)
#define for0(ii,bb) FOR(ii,0,bb)
#define for1(ii,bb) FOR(ii,1,bb+1)
#define pb push_back
#define mp make_pair
#define st first
#define nd second
#define pii pair<int,int>
#define piii pair<pii,int>
#define sp " "
#define nl "\n"
#define all(x) x.begin(),x.end()
#define fastio() ios_base::sync_with_stdio(0);cin.tie(0);
#define ll long long

using namespace std;

const int N = 100005;
const ll mod = 1e9+7;

int n,par[N];
ll h[N],w[N],ans;
bool d[N];

bool f(int x,int y){
    return h[x]>h[y];
}

ll comb2(ll x){
    x%=mod;
    return x*(x-1)/2%mod;
}

ll rec(ll x,ll y){
    return comb2(x+1)*comb2(y+1)%mod;
}

int findSet(int x){
    if(par[x]<0)return x;
    return par[x]=findSet(par[x]);
}

void onion(int x,int y,ll high){
    x=findSet(x);
    y=findSet(y);
    ll h=(rec(high,w[x])+rec(high,w[y]))%mod;
    h=(rec(high,w[x]+w[y])-h+mod)%mod;
    ans=(ans+h)%mod;
    if(par[x]<par[y]){
        par[y]=x;
        w[x]=(w[x]+w[y])%mod;
    }
    else{
        if(par[x]==par[y])
            par[y]--;
        par[x]=y;
        w[y]=(w[x]+w[y])%mod;
    }
}

int32_t main(){
    fastio()
    cin >> n;
    vector<int> vec;
    for0(i,n)
        cin >> h[i];
    for0(i,n){
        cin >> w[i];
        vec.pb(i);
    }
    memset(par,-1,N);
    sort(vec.begin(),vec.end(),f);
    for0(i,n)
        ans+=rec(h[i],w[i]);
    for(int i:vec){
        if(i!=0&&d[i-1])onion(i-1,i,h[i]);
        if(i!=n-1&&d[i+1])onion(i,i+1,h[i]);
        d[i]=1;
    }
    cout << ans << nl;
}

Compilation message

fancyfence.cpp: In function 'int32_t main()':
fancyfence.cpp:72:20: warning: 'memset' used with length equal to number of elements without multiplication by element size [-Wmemset-elt-size]
   72 |     memset(par,-1,N);
      |                    ^

Subtask #1
0.0 / 0.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct

Subtask #2
12.0 / 12.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct

Subtask #3
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Runtime error 191 ms 262148 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #4
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 4 ms 876 KB Output is correct
3 Runtime error 176 ms 262148 KB Execution killed with signal 9
4 Halted 0 ms 0 KB -

Subtask #5
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 4 ms 876 KB Output is correct
4 Runtime error 177 ms 262148 KB Execution killed with signal 9
5 Halted 0 ms 0 KB -

Subtask #6
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 512 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Correct 1 ms 492 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 1 ms 492 KB Output is correct
14 Correct 1 ms 492 KB Output is correct
15 Correct 46 ms 492 KB Output is correct
16 Correct 1 ms 492 KB Output is correct

Subtask #7
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 492 KB Output is correct
8 Correct 32 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 1 ms 492 KB Output is correct
11 Runtime error 173 ms 262148 KB Execution killed with signal 9
12 Halted 0 ms 0 KB -