제출 #1364188

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1364188		horiaboeriu	Fancy Fence (CEOI20_fancyfence)	C++20	100 / 100	18 ms	3124 KiB

fancyfence

#include <iostream>

using namespace std;
const int MAXN = 100000;
const int MOD = 1e9 + 7;
const int INF = 2e9;
int v[MAXN + 2], h[MAXN + 1], vst[MAXN + 1], vdr[MAXN + 1], st[MAXN + 1];
long long sp[MAXN + 1];
int gauss(int x) {
    return (long long)x * (x + 1) / 2 % MOD;
}
int main()
{
    int n, i, vf, rez, p, s, g;
    scanf("%d", &n);
    for (i = 1; i <= n; i++) {
        scanf("%d", &h[i]);
    }
    v[0] = v[n + 1] = 0;
    vf = 0;
    for (i = 1; i <= n; i++) {
        scanf("%d", &v[i]);
        sp[i] = sp[i - 1] + v[i];
        while (h[i] < h[st[vf]]) {
            vf--;
        }
        vst[i] = st[vf];
        vf++;
        st[vf] = i;
    }
    vf = 0;
    st[0] = n + 1;
    for (i = n; i > 0; i--) {
        while (h[i] <= h[st[vf]]) {
            vf--;
        }
        vdr[i] = st[vf];
        vf++;
        st[vf] = i;
    }
    //in stanga primul <= ca mine si in dreapta primul < ca mine
    //fixez primul minim din secventa
    //si sunt 4 cazuri
    //daca iau blocul in intregime sau nu iau un sufix sau nu iau un prefix sau iau doar din blocul respectiv
    rez = 0;
    for (i = 1; i <= n; i++) {
        p = (sp[i - 1] - sp[vst[i]]) % MOD;
        s = (sp[vdr[i] - 1] - sp[i]) % MOD;
        g = gauss(h[i]);
        rez = (rez + (long long)g * p % MOD * s) % MOD;//tot blocul
        rez = (rez + (long long)g * p % MOD * v[i]) % MOD;//inmultesc cu v[i] ca e pozitia unde se termina ca aleg prefixiul
        rez = (rez + (long long)g * s % MOD * v[i]) % MOD;//inmultesc cu v[i] ca e pozitia unde se incepe ca aleg sufixul
        //pana acum am ales strict ceva din prefix sau sufix
        //deci acum voi lua doar din blocul lui i
        rez = (rez + (long long)g * gauss(v[i])) % MOD;
    }
    printf("%d\n", rez);
    return 0;
}

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

fancyfence.cpp: In function 'int main()':
fancyfence.cpp:15:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     scanf("%d", &n);
      |     ~~~~~^~~~~~~~~~
fancyfence.cpp:17:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   17 |         scanf("%d", &h[i]);
      |         ~~~~~^~~~~~~~~~~~~
fancyfence.cpp:22:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   22 |         scanf("%d", &v[i]);
      |         ~~~~~^~~~~~~~~~~~~

• 서브태스크 1: 0 / 0
• 서브태스크 2: 12 / 12
• 서브태스크 3: 13 / 13
• 서브태스크 4: 15 / 15
• 서브태스크 5: 15 / 15
• 서브태스크 6: 18 / 18
• 서브태스크 7: 27 / 27