oj.uz

Submission #961194

# Submission time Handle Problem Language Result Execution time Memory
961194 2024-04-11T16:33:39 Z _rain_ Foehn Phenomena (JOI17_foehn_phenomena) C++14
30 / 100
 374 ms 15476 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
        {
            int lazy;
            int 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)
        {
            int& 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 , int 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);
        }
        int 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, int)':
foehn_phenomena.cpp:69:23: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   69 |             int m = l + r >> 1;
      |                     ~~^~~
foehn_phenomena.cpp: In member function 'int 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 3 ms 604 KB Output is correct
5 Correct 3 ms 476 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 604 KB Output is correct
9 Correct 3 ms 604 KB Output is correct
10 Correct 3 ms 604 KB Output is correct
11 Correct 3 ms 604 KB Output is correct
12 Correct 3 ms 600 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 2 ms 600 KB Output is correct
15 Correct 3 ms 604 KB Output is correct
16 Correct 2 ms 600 KB Output is correct
17 Correct 2 ms 604 KB Output is correct
18 Correct 2 ms 584 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 1 ms 348 KB Output is correct

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 361 ms 14420 KB Output is correct
2 Correct 374 ms 14768 KB Output is correct
3 Correct 363 ms 15476 KB Output is correct
4 Incorrect 350 ms 15020 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 3 ms 604 KB Output is correct
5 Correct 3 ms 476 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 604 KB Output is correct
9 Correct 3 ms 604 KB Output is correct
10 Correct 3 ms 604 KB Output is correct
11 Correct 3 ms 604 KB Output is correct
12 Correct 3 ms 600 KB Output is correct
13 Correct 2 ms 604 KB Output is correct
14 Correct 2 ms 600 KB Output is correct
15 Correct 3 ms 604 KB Output is correct
16 Correct 2 ms 600 KB Output is correct
17 Correct 2 ms 604 KB Output is correct
18 Correct 2 ms 584 KB Output is correct
19 Correct 1 ms 344 KB Output is correct
20 Correct 1 ms 344 KB Output is correct
21 Correct 1 ms 348 KB Output is correct
22 Correct 361 ms 14420 KB Output is correct
23 Correct 374 ms 14768 KB Output is correct
24 Correct 363 ms 15476 KB Output is correct
25 Incorrect 350 ms 15020 KB Output isn't correct
26 Halted 0 ms 0 KB -