oj.uz

Submission #877254

# Submission time Handle Problem Language Result Execution time Memory
877254 2023-11-23T05:01:05 Z hasan2006 Foehn Phenomena (JOI17_foehn_phenomena) C++17
40 / 100
 915 ms 29024 KB 
#include <bits/stdc++.h>

using namespace std;

#define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
#define rall(s) s.rbegin(),s.rend()
#define all(s) s.begin(),s.end()
#define pb push_back
#define se second
#define fi first
#define ll long long
#define ld long double
#define YES cout<<"YES\n"
#define Yes cout<<"Yes\n"
#define yes cout<<"yes\n"
#define NO cout<<"NO\n"
#define No cout<<"No\n"
#define no cout<<"no\n"


const int N = 5e5 + 9 , mod = 1e9 + 7;
ll   a[N] = {}, b[N] , c[N] , d[N] , tree[N] , lz[N];


void lazzy(int i , int l , int r){
    tree[i] += lz[i] * (r - l + 1);
    lz[2 * i] += lz[i];
    lz[2 * i + 1] += lz[i];
    lz[i] = 0;
}

ll ind;
void get(int i , int l , int r , int x , int y ,int k){
    int m = (l + r) / 2;
    if(x > r || y < l){
        return;
    }
    lazzy(i , l,  r);
    if(l >= x && r <= y){
        tree[i] += (r - l + 1) * k;
        ind = tree[i];
        lz[2 * i] += k;
        lz[2 * i + 1] += k;
        return;
    }
    get(2 * i , l ,  m , x , y , k);
    get(2 * i + 1 , m + 1 , r , x , y , k);
    tree[i] = tree[2 * i] + tree[2 * i + 1];
}

void solve()
{
    ll q , i , j , m ,n, z ,s = 0 , f, l , r , k , x , y , mn  = 1e18 , mx = 0;
    cin>>n>>m>>x>>y;
    for(i = 0; i <= n; i++){
        cin>>a[i];
        if(i > 1)
            b[i - 1] = b[i - 2] , c[i - 1] = c[i - 2];
        if(i && a[i] >= a[i - 1]){
            s -= abs(a[i] - a[i - 1]) * x;
            b[i - 1]++;
        }else {
            s += abs(a[i] - a[i - 1]) * y;
            c[i - 1]++;
        }
    }
    while(m--){
        cin>>l>>r>>k;
        vector<ll>v;
        get(1 , 1 , n , l, r , k);
        if(l == 1)
            v.pb(0);
        else {
            get(1 , 1  , n , l - 1, l - 1 , 0);
            v.pb(ind + a[l - 1]);
        }
        get(1 , 1 , n , l, l , 0);
        v.pb(ind + a[l]);
        get(1 , 1 , n , r, r , 0);
        v.pb(ind + a[r]);
        if(r != n){
            get(1 , 1 , n , r + 1, r  + 1, 0);
            v.pb(ind + a[r + 1]);
        }
        if(v[0] <= (v[1] - k)){
            s += abs((v[1] - k) - v[0]) * x;
        }else {
            s -= abs((v[1] - k) - v[0]) * y;
        }
        if(v[0] <= v[1]){
            s -= abs(v[1] - v[0]) * x;
        }else {
            s += abs(v[1] - v[0]) * y;
        }
        if(r < n){
            if((v[2] - k) <= v[3]){
                s += abs(v[3] - (v[2] - k)) * x;
            }else {
                s -= abs(v[3] - (v[2] - k)) * y;
            }
            if(v[2] <= v[3]){
                s -= abs(v[3] - v[2]) * x;
            }else {
                s += abs(v[3] - v[2]) * y;
            }
        }
        cout<<s<<"\n";
    }
}

int main(){
 
int t = 1;
//cin>>t;
while(t--)
     {
     solve();
     }
}
// Author : حسن

Compilation message

foehn_phenomena.cpp: In function 'void solve()':
foehn_phenomena.cpp:53:8: warning: unused variable 'q' [-Wunused-variable]
   53 |     ll q , i , j , m ,n, z ,s = 0 , f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |        ^
foehn_phenomena.cpp:53:16: warning: unused variable 'j' [-Wunused-variable]
   53 |     ll q , i , j , m ,n, z ,s = 0 , f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                ^
foehn_phenomena.cpp:53:26: warning: unused variable 'z' [-Wunused-variable]
   53 |     ll q , i , j , m ,n, z ,s = 0 , f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                          ^
foehn_phenomena.cpp:53:37: warning: unused variable 'f' [-Wunused-variable]
   53 |     ll q , i , j , m ,n, z ,s = 0 , f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                     ^
foehn_phenomena.cpp:53:60: warning: unused variable 'mn' [-Wunused-variable]
   53 |     ll q , i , j , m ,n, z ,s = 0 , f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                                            ^~
foehn_phenomena.cpp:53:73: warning: unused variable 'mx' [-Wunused-variable]
   53 |     ll q , i , j , m ,n, z ,s = 0 , f, l , r , k , x , y , mn  = 1e18 , mx = 0;
      |                                                                         ^~

Subtask #1
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4556 KB Output is correct
2 Correct 12 ms 6748 KB Output is correct
3 Correct 9 ms 6756 KB Output is correct
4 Correct 7 ms 2712 KB Output is correct
5 Correct 11 ms 6744 KB Output is correct
6 Correct 7 ms 6744 KB Output is correct
7 Correct 7 ms 8540 KB Output is correct
8 Correct 8 ms 8796 KB Output is correct
9 Correct 8 ms 8696 KB Output is correct
10 Correct 7 ms 6748 KB Output is correct
11 Correct 10 ms 2648 KB Output is correct
12 Correct 7 ms 2504 KB Output is correct
13 Correct 8 ms 8724 KB Output is correct
14 Correct 9 ms 6492 KB Output is correct
15 Correct 7 ms 8540 KB Output is correct
16 Correct 7 ms 8540 KB Output is correct
17 Correct 6 ms 8716 KB Output is correct
18 Correct 7 ms 8536 KB Output is correct
19 Correct 1 ms 8632 KB Output is correct
20 Correct 1 ms 8540 KB Output is correct
21 Correct 2 ms 8636 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 861 ms 27972 KB Output is correct
2 Correct 915 ms 27472 KB Output is correct
3 Correct 819 ms 29024 KB Output is correct
4 Correct 853 ms 28564 KB Output is correct
5 Correct 785 ms 28396 KB Output is correct
6 Correct 526 ms 26340 KB Output is correct
7 Correct 517 ms 26868 KB Output is correct
8 Correct 765 ms 28396 KB Output is correct
9 Correct 703 ms 28756 KB Output is correct
10 Correct 676 ms 27336 KB Output is correct
11 Correct 607 ms 26452 KB Output is correct
12 Correct 508 ms 26976 KB Output is correct
13 Correct 576 ms 27644 KB Output is correct

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 4556 KB Output is correct
2 Correct 12 ms 6748 KB Output is correct
3 Correct 9 ms 6756 KB Output is correct
4 Correct 7 ms 2712 KB Output is correct
5 Correct 11 ms 6744 KB Output is correct
6 Correct 7 ms 6744 KB Output is correct
7 Correct 7 ms 8540 KB Output is correct
8 Correct 8 ms 8796 KB Output is correct
9 Correct 8 ms 8696 KB Output is correct
10 Correct 7 ms 6748 KB Output is correct
11 Correct 10 ms 2648 KB Output is correct
12 Correct 7 ms 2504 KB Output is correct
13 Correct 8 ms 8724 KB Output is correct
14 Correct 9 ms 6492 KB Output is correct
15 Correct 7 ms 8540 KB Output is correct
16 Correct 7 ms 8540 KB Output is correct
17 Correct 6 ms 8716 KB Output is correct
18 Correct 7 ms 8536 KB Output is correct
19 Correct 1 ms 8632 KB Output is correct
20 Correct 1 ms 8540 KB Output is correct
21 Correct 2 ms 8636 KB Output is correct
22 Correct 861 ms 27972 KB Output is correct
23 Correct 915 ms 27472 KB Output is correct
24 Correct 819 ms 29024 KB Output is correct
25 Correct 853 ms 28564 KB Output is correct
26 Correct 785 ms 28396 KB Output is correct
27 Correct 526 ms 26340 KB Output is correct
28 Correct 517 ms 26868 KB Output is correct
29 Correct 765 ms 28396 KB Output is correct
30 Correct 703 ms 28756 KB Output is correct
31 Correct 676 ms 27336 KB Output is correct
32 Correct 607 ms 26452 KB Output is correct
33 Correct 508 ms 26976 KB Output is correct
34 Correct 576 ms 27644 KB Output is correct
35 Correct 809 ms 28108 KB Output is correct
36 Incorrect 768 ms 28620 KB Output isn't correct
37 Halted 0 ms 0 KB -