Submission #1282967

#	Time	Username	Problem	Language	Result	Execution time	Memory
1282967		thanhcodedao	Fancy Fence (CEOI20_fancyfence)	C++20	55 / 100	16 ms	1204 KiB

fancyfence

/****ThanhCodeDao*****/
/*******Azazel*******/
#include<bits/stdc++.h>
using namespace std;

#define F first
#define S second
#define pb push_back
#define checkbit(mask,i) ((mask>>i)&1)
#define bit(i) (1<<i)
#define MLog 21
#define all(v) v.begin(), v.end()
#define uni(v) v.erase(unique(all(v)), v.end())
typedef long long ll;
const ll maxN = 1e5+3, modd = 1e9+7, nd2 = 500000004;
struct Point{
    ll x,y;
};
ll cross(Point p,Point q,Point r){ // vi tri r voi duong pq >0 la ben trai, =0 la thang hang
    ll val = (q.x-p.x)*(r.y-q.y) - (q.y-p.y)*(r.x-q.x);
    if(val < 0) return -1;
    if(val > 0) return 1;
    return 0;
}
ll dot(Point vecA,Point vecB){ // tra ve >0 la nhon, <0 la tu, =0 la vuong, 2 vecto phai chung goc
    ll val = vecA.x*vecB.x + vecA.y*vecB.y;
    if(val < 0) return -1;
    if(val > 0) return 1;
    return 0;
}
double triarea(Point p,Point q,Point r){ // cross(pq * pr) / 2
    double cross = (q.x-p.x)*(r.y-q.y) - (q.y-p.y)*(r.x-q.x);
    return fabs(cross)/2.0;
}
/* de cho

*/
/* nhan xet nho

*/
/* nhan xet tu thuat trau
*/
int n;
int h[maxN], w[maxN];
ll ltnp(ll a,ll b){
    if(b==0) return 1;
    if(b==1) return a;
    ll half = ltnp(a,b/2) % modd;
    if(b%2){
        return ((half*half)%modd * a)%modd;
    }else{
        return (half*half)%modd;
    }
}
ll calc(ll sz){
    return ((sz * (sz+1))%modd * nd2)%modd;
}
bool checksub4(){
    for(int i = 2;i<=n;i++){
        if(h[i] != h[i-1]) return false;
    }
    return true;
}
void sub4(){
    ll sumw = 0;
    for(int i = 1;i<=n;i++) sumw += w[i];
    sumw %= modd;
    cout << ((calc(h[1]) * calc(sumw))%modd);
}
bool checksub2(){
    for(int i = 1;i<=n;i++){
        if(h[i] == 1 or h[i] == 2) continue;
        return false;
    }
    return true;
}
void sub2(){
    ll ans = 0;
    // h = 1
    ll sumw = 0;
    for(int i = 1;i<=n;i++) sumw += w[i];
    sumw %= modd;
    ans = calc(sumw);
    // h2
    for(int i = 1;i<=n;i++){
        if(h[i] == 1) continue; // chi tinh h = 2
        int j = i;
        ll sumw = w[j];
        while(j+1<=n and h[i] == h[j+1]){
            sumw += w[j+1];
            j++;
        }
        sumw %= modd;
        ll res = (calc(h[i]) * calc(sumw))%modd;
        res = (res - calc(sumw) + modd)%modd;
        (ans += res)%=modd;
        i = j;
    }
    cout << ans;
}
bool checksub1(){
    if(n>50) return false;
    for(int i = 1;i<=n;i++){
        if(h[i] > 50) return false;
        if(w[i] > 50) return false;
    }
    return true;
}
int sum[100][100];
int getsum(int stx,int sty,int fnx,int fny){
    return sum[fnx][fny] - sum[fnx][sty-1] - sum[stx-1][fny] + sum[stx-1][sty-1];
}
void sub1(){
    int mxw = 0;
    int mxh = 0;
    int ans = 0;
    for(int i = 1;i<=n;i++){
        for(int z = 1;z<=w[i];z++){
            ++mxw;
            for(int j = 1;j<=h[i];j++){
                sum[j][mxw] = 1;
            }
        }
        mxh = max(mxh,h[i]);
    }
    for(int i = 1;i<=mxh;i++){
        for(int j = 1;j<=mxw;j++){
            sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + sum[i][j];
        }
    }
    for(int dai = 1;dai<=mxh;dai++){
        for(int rong = 1;rong<=mxw;rong++){
            for(int i = 1;i<=mxh;i++){
                for(int j = 1;j<=mxw;j++){
                    int nxti = i + dai - 1, nxtj = j + rong - 1;
                    if(nxti <= mxh and nxtj <= mxw and getsum(i,j,nxti,nxtj) == (dai*rong)){
                        ++ans;
                    }
                }
            }
        }
    }
    cout << ans;
}
bool checksub5(){
    for(int i = 1;i<=n-1;i++){
        if(h[i] <= h[i+1]) continue;
        return false;
    }
    return true;
}
void sub5(){
    ll sumw = 0;
    for(int i = 1;i<=n;i++){
        (sumw += w[i])%=modd;
    }
    ll ans = 0;
    ll preh = 0;
    for(int i = 1;i<=n;i++){
//        cout << sumw << '\n';
        ll cur =  (calc(h[i]) * (calc(sumw)))%modd;
        (ans += cur)%=modd;
        ans = (ans - (calc(preh)*calc(sumw))%modd + modd)%modd;
        (ans += modd)%=modd;
        preh = h[i];

        int j = i;
        (sumw = sumw - w[j] + modd)%=modd;
        while(j+1<=n and h[j+1] == h[i]){
            (sumw = sumw - w[j+1] + modd)%=modd;
            ++j;
        }
        i = j;
    }
    cout << ans;
}
void solve() {
    cin >> n;
    for(int i = 1;i<=n;i++) cin >> h[i];
    for(int i = 1;i<=n;i++) cin >> w[i];
    if(checksub5()){
        sub5();
        return;
    }
    if(checksub4()){
        sub4();
        return;
    }
    if(checksub2()){
        sub2();
        return;
    }
    if(checksub1()){
        sub1();
        return;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
//    freopen("inp.txt","r",stdin);
    //freopen("out.txt","w",stdout);
    solve();
    return 0;
}

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