oj.uz

Submission #880476

# Submission time Handle Problem Language Result Execution time Memory
880476 2023-11-29T13:23:21 Z cpptowin Foehn Phenomena (JOI17_foehn_phenomena) C++17
40 / 100
 140 ms 17304 KB 
#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 5010
#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;
struct Fenwick_Tree
{
    int bit_add[maxn],bit_sub[maxn];

    void update(int u, int v, int val)
    {
        for (int i = u; i <= maxn; i += i & -i)
        {
            bit_add[i] += val;
            bit_sub[i] += 1LL * (u - 1) * val;
        }
        for (int i = v; i <= maxn; i += i & -i)
        {
            bit_add[i] -= val;
            bit_sub[i] -= 1LL * v * val;
        }
    }

    void update(int u, int val)
    {
        update(u, u, val);
    }

    int get(int u)
    {
        if(u < 0) return 0;
        int ans1 = 0, ans2 = 0;
        for (int i = u; i; i -= i & -i)
        {
            ans1 += bit_add[i];
            ans2 += bit_sub[i];
        }
        return u * ans1 - ans2;
    }

    int get(int l, int r)
    {
        return get(r) - get(l - 1);
    }
} t1;
int a[N];
int n,q,s,t;
int ans;
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);
    cin >> n >> q >> s >> t;
    fo(i,0,n)
    {
        cin >> a[i];
        ans += ((a[i - 1] - a[i] < 0) ? s : t) * (a[i - 1] - a[i]);
    }
    fo(i,1,n) t1.update(i,i,a[i]);
    while(q--)
    {
        int l,r,add;
        cin >> l >> r >> add;
        int val = ((t1.get(l - 1,l - 1) - t1.get(l,l) < 0) ? s : t) * (t1.get(l - 1,l - 1) - t1.get(l,l));
        ans -= val;
//        cout << val << ' ' << ans << "\n";
        if(r < n)
        {
            val = ((t1.get(r,r) - t1.get(r + 1,r + 1) < 0) ? s : t) * (t1.get(r,r) - t1.get(r + 1,r + 1));
            ans -= val;
        }
        t1.update(max(l,1LL),r,add);
        val = ((t1.get(l - 1,l - 1) - t1.get(l,l) < 0) ? s : t) * (t1.get(l - 1,l - 1) - t1.get(l,l));
        ans += val;
//        cout << val << ' ' << ans << "\n";
        if(r < n)
        {
            val = ((t1.get(r,r) - t1.get(r + 1,r + 1) < 0) ? s : t) * (t1.get(r,r) - t1.get(r + 1,r + 1));
            ans += val;
        }
        cout << ans;
        en;
//        fo(i,1,n) cout << t1.get(i,i) << ' ';
//        en;
    }
}

Compilation message

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

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10588 KB Output is correct
2 Correct 3 ms 10832 KB Output is correct
3 Correct 3 ms 10840 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 4 ms 10844 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct
7 Correct 3 ms 10844 KB Output is correct
8 Correct 3 ms 10844 KB Output is correct
9 Correct 3 ms 10588 KB Output is correct
10 Correct 3 ms 10820 KB Output is correct
11 Correct 3 ms 10844 KB Output is correct
12 Correct 3 ms 10844 KB Output is correct
13 Correct 3 ms 10844 KB Output is correct
14 Correct 3 ms 10776 KB Output is correct
15 Correct 3 ms 10588 KB Output is correct
16 Correct 3 ms 10844 KB Output is correct
17 Correct 2 ms 10840 KB Output is correct
18 Correct 3 ms 10840 KB Output is correct
19 Correct 2 ms 10588 KB Output is correct
20 Correct 1 ms 10588 KB Output is correct
21 Correct 1 ms 10704 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 126 ms 15340 KB Output is correct
2 Correct 140 ms 16000 KB Output is correct
3 Correct 135 ms 16412 KB Output is correct
4 Correct 133 ms 15664 KB Output is correct
5 Correct 126 ms 16724 KB Output is correct
6 Correct 103 ms 16464 KB Output is correct
7 Correct 107 ms 16300 KB Output is correct
8 Correct 122 ms 16720 KB Output is correct
9 Correct 128 ms 17304 KB Output is correct
10 Correct 132 ms 15880 KB Output is correct
11 Correct 93 ms 16212 KB Output is correct
12 Correct 104 ms 16724 KB Output is correct
13 Correct 97 ms 17200 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 10588 KB Output is correct
2 Correct 3 ms 10832 KB Output is correct
3 Correct 3 ms 10840 KB Output is correct
4 Correct 2 ms 10844 KB Output is correct
5 Correct 4 ms 10844 KB Output is correct
6 Correct 3 ms 10844 KB Output is correct
7 Correct 3 ms 10844 KB Output is correct
8 Correct 3 ms 10844 KB Output is correct
9 Correct 3 ms 10588 KB Output is correct
10 Correct 3 ms 10820 KB Output is correct
11 Correct 3 ms 10844 KB Output is correct
12 Correct 3 ms 10844 KB Output is correct
13 Correct 3 ms 10844 KB Output is correct
14 Correct 3 ms 10776 KB Output is correct
15 Correct 3 ms 10588 KB Output is correct
16 Correct 3 ms 10844 KB Output is correct
17 Correct 2 ms 10840 KB Output is correct
18 Correct 3 ms 10840 KB Output is correct
19 Correct 2 ms 10588 KB Output is correct
20 Correct 1 ms 10588 KB Output is correct
21 Correct 1 ms 10704 KB Output is correct
22 Correct 126 ms 15340 KB Output is correct
23 Correct 140 ms 16000 KB Output is correct
24 Correct 135 ms 16412 KB Output is correct
25 Correct 133 ms 15664 KB Output is correct
26 Correct 126 ms 16724 KB Output is correct
27 Correct 103 ms 16464 KB Output is correct
28 Correct 107 ms 16300 KB Output is correct
29 Correct 122 ms 16720 KB Output is correct
30 Correct 128 ms 17304 KB Output is correct
31 Correct 132 ms 15880 KB Output is correct
32 Correct 93 ms 16212 KB Output is correct
33 Correct 104 ms 16724 KB Output is correct
34 Correct 97 ms 17200 KB Output is correct
35 Correct 126 ms 15396 KB Output is correct
36 Incorrect 139 ms 16728 KB Output isn't correct
37 Halted 0 ms 0 KB -