oj.uz

Submission #997333

# Submission time Handle Problem Language Result Execution time Memory
997333 2024-06-12T07:10:13 Z Malix Foehn Phenomena (JOI17_foehn_phenomena) C++14
30 / 100
 591 ms 15696 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vii;
typedef pair<int,int> pi;
typedef vector<pi> pii;
typedef tuple<int,int,int> tii;

#define REP(i,a,b) for(int i=a;i<b;i++)
#define F first
#define S second
#define PB push_back
#define MP make_pair
#define LSOne(s) ((s)&(-s))

ll INF=1e18+10;
int inf=1e9+10;
ll M=1e9+7;

vector<ll> a,b;

void update(int l,int r,int k,int x,int y,int z){
    if(x>y)return;
    //cout<<l<<" "<<r<<" "<<x<<" "<<y<<"\n";
    if(l==x&&r==y)b[k]+=z;
    else{
        int m=(l+r)/2;
        update(l,m,k*2,x,min(m,y),z);
        update(m+1,r,k*2+1,max(x,m+1),y,z);
    }
}

ll find(int l,int r,int k,ll v){
    if(l==r)return a[v]+b[k];
    int m=(l+r)/2;
    if(v>m)return b[k]+find(m+1,r,k*2+1,v);
    else return b[k]+find(l,m,k*2,v);
}

int main() {   
//ios::sync_with_stdio(0);
//cin.tie(0);
//freopen("test_input.txt", "r", stdin);
//freopen("test_output.txt", "w", stdout);
    int n,q;ll s,t;
    cin>>n>>q>>s>>t;
    n++;
    a.resize(n);
    REP(i,0,n)cin>>a[i];
    b.resize(4*n+1,0);
    int x=0,y=0;
    vi cu(n,0);
    REP(i,0,n-1)(a[i]<a[i+1]?x+=abs(a[i]-a[i+1]):y+=abs(a[i]-a[i+1]));
    REP(i,0,n-1)if(a[i]<a[i+1])cu[i]=1;
    while(q--){
        int c,d,e;cin>>c>>d>>e;
        ll g1=find(0,n-1,1,c-1);
        ll g2=find(0,n-1,1,c);
        if(cu[c-1])x-=abs(g1-g2);
        else y-=abs(g1-g2);
        if(d!=n-1){
            g1=find(0,n-1,1,d);
            g2=find(0,n-1,1,d+1);
            if(cu[d])x-=abs(g1-g2);
            else y-=abs(g1-g2);
        }
        update(0,n-1,1,c,d,(ll)e);
        ll val1=find(0,n-1,1,c-1);
        ll val2=find(0,n-1,1,c);
        //cout<<val1<<" "<<val2<<"\n";
        if(val1<val2){
            cu[c-1]=1;
            x+=abs(val1-val2);
        }
        else{
            cu[c-1]=0;
            y+=abs(val1-val2);
        }
        if(d!=n-1){
            val1=find(0,n-1,1,d);
            val2=find(0,n-1,1,d+1);//cout<<val1<<" "<<val2<<"\n";
            if(val1<val2){
                cu[d]=1;
                x+=abs(val1-val2);
            }
            else{
                cu[d]=0;
                y+=abs(val1-val2);
            }
        }
        //cout<<x<<" "<<y<<"\n";
        cout<<t*y-x*s<<"\n";
    }
}

Subtask #1
30.0 / 30.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 591 ms 15696 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 60.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 348 KB Output is correct
2 Correct 5 ms 568 KB Output is correct
3 Correct 5 ms 348 KB Output is correct
4 Correct 5 ms 348 KB Output is correct
5 Correct 5 ms 348 KB Output is correct
6 Correct 9 ms 348 KB Output is correct
7 Correct 5 ms 348 KB Output is correct
8 Correct 5 ms 452 KB Output is correct
9 Correct 7 ms 600 KB Output is correct
10 Correct 5 ms 348 KB Output is correct
11 Correct 5 ms 444 KB Output is correct
12 Correct 5 ms 600 KB Output is correct
13 Correct 4 ms 568 KB Output is correct
14 Correct 5 ms 604 KB Output is correct
15 Correct 5 ms 348 KB Output is correct
16 Correct 4 ms 444 KB Output is correct
17 Correct 4 ms 344 KB Output is correct
18 Correct 4 ms 348 KB Output is correct
19 Correct 0 ms 348 KB Output is correct
20 Correct 0 ms 348 KB Output is correct
21 Correct 0 ms 348 KB Output is correct
22 Incorrect 591 ms 15696 KB Output isn't correct
23 Halted 0 ms 0 KB -