oj.uz

Submission #961195

# Submission time Handle Problem Language Result Execution time Memory
961195 2024-04-11T16:34:33 Z _rain_ Foehn Phenomena (JOI17_foehn_phenomena) C++14
30 / 100
 381 ms 16208 KB 
/** author : _RAIN_ **/
#include<bits/stdc++.h>
using namespace std;

using i64 = long long;
using ui64 = unsigned long long;

#define MASK(x) ((i64)(1) << (x))
#define BIT(mask , x) (((mask) >> (x)) & (1))

template<class T>
    bool maximize(T &a , T b) {if (a < b) return a = b , true; else return false;}
template<class T>
    bool minimize(T &a , T b) {if (a > b) return a = b , true; else return false;}
template<class T>
    T gcd(T x , T y) {while (y) swap(y , x %= y); return x;}
template<class T>
    T lcm(T x , T y) {return (x * y) / gcd(x , y);}

const int maxn = 2e5;
int numhouse , q ;
int a[maxn + 2];
i64 s , t;

class interval
{
    public:
        struct NODE
        {
            i64 lazy;
            i64 val;
        };
        vector<NODE> seg;
        void init(int n)
        {
            seg.assign(n * 4 + 7 , {0 , 0});

        }
        void build(int node , int l , int r , int a[])
        {
            if (l == r) 
                seg[node].val = a[l];
            else 
            {
                int m = l + r >> 1;
                build(node * 2 , l , m , a);
                build(node * 2 + 1 , m + 1 , r , a);
                seg[node].val = seg[node * 2].val + seg[node * 2 + 1].val;
            }
            return;
        }
        void pushdown(int node)
        {
            i64& t = seg[node].lazy;
            seg[node * 2].val += t; seg[node * 2].lazy += t;
            seg[node * 2 + 1].val  += t; seg[node * 2 + 1].lazy += t;
            t = 0;
            return;
        }
        void update(int node , int l , int r , int u , int v , i64 k)
        {
            if (l > v  || r < u) return;
            if (u <= l && r <= v)
            {
                seg[node].val += k;
                seg[node].lazy += k;
                return;
            }
            int m = l + r >> 1;
            pushdown(node);
            update(node * 2 , l , m , u , v , k);
            update(node * 2 + 1 , m + 1 , r , u , v , k);
        }
        i64 get(int node , int l , int r , int u , int v)
        {
            if (l > v || r < u) return 0;
            if (u <= l && r <= v) return seg[node].val;
            int m = l + r >> 1;
            pushdown(node);
            return get(node * 2 , l , m , u , v) + get(node * 2 + 1, m + 1 , r , u , v);
        }
};

int32_t main(void)
{
    cin.tie(nullptr)->sync_with_stdio(false);
    const string name = "main";
    if (fopen((name + ".inp").c_str() , "r"))
    {
        (void)!freopen((name + ".inp").c_str() , "r" , stdin);
        (void)!freopen((name + ".out").c_str() , "w+", stdout);
    }
    cin >> numhouse >> q >> s >> t;
    interval seg; seg.init(numhouse);
    for (int i = 0; i <= numhouse; ++i) 
        cin >> a[i];
    seg.build(1 , 0 , numhouse , a);
    i64 answer = 0;
    for (int i = 1; i <= numhouse; ++i)
    {
        if (a[i] > a[i - 1]) answer -= s * (a[i] - a[i - 1]);
        if (a[i] <= a[i - 1]) answer += t * (a[i - 1] - a[i]);
    }
    auto cost = [&](int l , int r)->i64
    {
        int x = seg.get(1 , 0 , numhouse , l , l);
        int y = seg.get(1 , 0 , numhouse , r , r);
        return (i64)(x > y ? t : -s) * abs(x - y);
    };

    while(q--)
    {
        int l , r , x; cin>>l>>r>>x;
        if (l > 0) answer-= cost(l - 1 , l);
        if (r < numhouse) answer-=cost(r , r + 1);
        seg.update(1 , 0 , numhouse , l , r , x);
        if (l > 0) answer+=cost(l - 1 , l);
        if (r < numhouse) answer+=cost(r , r + 1);
        cout<<answer<<'\n';
    }
}

Compilation message

foehn_phenomena.cpp: In member function 'void interval::build(int, int, int, int*)':
foehn_phenomena.cpp:45:27: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   45 |                 int m = l + r >> 1;
      |                         ~~^~~
foehn_phenomena.cpp: In member function 'void interval::update(int, int, int, int, int, i64)':
foehn_phenomena.cpp:69:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |             int m = l + r >> 1;
      |                     ~~^~~
foehn_phenomena.cpp: In member function 'i64 interval::get(int, int, int, int, int)':
foehn_phenomena.cpp:78:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   78 |             int m = l + r >> 1;
      |                     ~~^~~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 600 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 4 ms 600 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Correct 3 ms 600 KB Output is correct
9 Correct 3 ms 600 KB Output is correct
10 Correct 3 ms 600 KB Output is correct
11 Correct 3 ms 600 KB Output is correct
12 Correct 3 ms 604 KB Output is correct
13 Correct 2 ms 600 KB Output is correct
14 Correct 3 ms 604 KB Output is correct
15 Correct 4 ms 604 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 2 ms 604 KB Output is correct
18 Correct 4 ms 860 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 344 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 358 ms 15136 KB Output is correct
2 Correct 366 ms 15664 KB Output is correct
3 Correct 381 ms 16208 KB Output is correct
4 Incorrect 365 ms 15524 KB Output isn't correct
5 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 600 KB Output is correct
2 Correct 3 ms 604 KB Output is correct
3 Correct 3 ms 604 KB Output is correct
4 Correct 4 ms 600 KB Output is correct
5 Correct 3 ms 604 KB Output is correct
6 Correct 3 ms 604 KB Output is correct
7 Correct 3 ms 604 KB Output is correct
8 Correct 3 ms 600 KB Output is correct
9 Correct 3 ms 600 KB Output is correct
10 Correct 3 ms 600 KB Output is correct
11 Correct 3 ms 600 KB Output is correct
12 Correct 3 ms 604 KB Output is correct
13 Correct 2 ms 600 KB Output is correct
14 Correct 3 ms 604 KB Output is correct
15 Correct 4 ms 604 KB Output is correct
16 Correct 2 ms 604 KB Output is correct
17 Correct 2 ms 604 KB Output is correct
18 Correct 4 ms 860 KB Output is correct
19 Correct 1 ms 348 KB Output is correct
20 Correct 1 ms 348 KB Output is correct
21 Correct 0 ms 344 KB Output is correct
22 Correct 358 ms 15136 KB Output is correct
23 Correct 366 ms 15664 KB Output is correct
24 Correct 381 ms 16208 KB Output is correct
25 Incorrect 365 ms 15524 KB Output isn't correct
26 Halted 0 ms 0 KB -