oj.uz

답안 #885519

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
885519 2023-12-09T22:47:06 Z Marco_Escandon Foehn Phenomena (JOI17_foehn_phenomena) C++11
100 / 100
 887 ms 24628 KB 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int long long
struct node
{
    int value, lazy;
 
    node(int v = 0LL)
    {
        value = v;
        lazy = 0LL;
    }
};
 
node tree[(int)1e6]; int l;
 
void update(int v, int s, int e, int k)
{
    tree[v].lazy += k;
    tree[v].value += (e - s + 1) * k;
}
 
void push(int v, int s, int e)
{
    if (tree[v].lazy)
    {
        int middle = (s + e) / 2;
 
        update(2 * v, s, middle, tree[v].lazy);
        update(2 * v + 1, middle + 1, e, tree[v].lazy);
 
        tree[v].lazy = 0LL;
    }
}
 
void increase(int node, int v, int x, int y, int s, int e)
{
    if (x > e || y < s) return;
 
    if (s >= x && e <= y)
    {
        update(node, s, e, v);
        return;
    }
 
    push(node, s, e);
 
    int middle = (s + e) / 2;
 
    increase(node * 2, v, x, y, s, middle);
    increase(node * 2 + 1, v, x, y, middle + 1, e);
 
    tree[node].value = tree[node * 2].value
        + tree[node * 2 + 1].value;
}
 
void increase(int x, int y, int v) { increase(1, v, x, y, 1, l); }
 
int sum(int node, int x, int y, int s, int e)
{
    if (x > e || y < s) return 0LL;
 
    if (s >= x && e <= y)
        return tree[node].value;
 
    push(node, s, e);
    int middle = (s + e) / 2;
 
    return sum(node * 2, x, y, s, middle) +
        sum(node * 2 + 1, x, y, middle + 1, e);
}
 
int query(int x) { return sum(1, x, x, 1, l); }
 
void Segment_tree(int n)
{
    for (l = 1; l < n; l = (l << 1));
}
 
 
int32_t main()
{
    ll n,q,s,t;
    cin>>n>>q>>s>>t;
    ll cad[n+1];
    Segment_tree (n+2);
    for(int i=0LL; i<n+1; i++)
    {
        cin>>cad[i];
    }
    ll sol=0LL;
    for(int i=1; i<=n; i++)
    {
        sol-=s*max(cad[i]-cad[i-1],0LL);
        sol+=t*max(cad[i-1]-cad[i],0LL);
        increase(i+1,i+1,cad[i]);
    }
    while(q--)
    {
        ll a,b,c;
        cin>>a>>b>>c;
        a++;
        b++;
        ll t1=query(a),t2=query(a-1);
        sol+=s*max(t1-t2,0LL);
        sol-=t*max(t2-t1,0LL);
        if(b!=n+1){
        ll t3=query(b+1), t4=query(b);
        sol+=s*max(t3-t4,0LL);
        sol-=t*max(t4-t3,0LL);}
 
        increase(a,b,c);
        t1=query(a),t2=query(a-1);

        sol-=s*max(t1-t2,0LL);
        sol+=t*max(t2-t1,0LL);
        if(b!=n+1){
        ll t3=query(b+1), t4=query(b);
        sol-=s*max(t3-t4,0LL);
        sol+=t*max(t4-t3,0LL);}
        cout<<sol<<"\n";
    }
}

Subtask #1
30.0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 15960 KB Output is correct
2 Correct 9 ms 15964 KB Output is correct
3 Correct 9 ms 15964 KB Output is correct
4 Correct 10 ms 15964 KB Output is correct
5 Correct 10 ms 16220 KB Output is correct
6 Correct 9 ms 15964 KB Output is correct
7 Correct 9 ms 15964 KB Output is correct
8 Correct 9 ms 15964 KB Output is correct
9 Correct 9 ms 15960 KB Output is correct
10 Correct 14 ms 15964 KB Output is correct
11 Correct 9 ms 15964 KB Output is correct
12 Correct 9 ms 15964 KB Output is correct
13 Correct 8 ms 15964 KB Output is correct
14 Correct 8 ms 15964 KB Output is correct
15 Correct 9 ms 16216 KB Output is correct
16 Correct 8 ms 15964 KB Output is correct
17 Correct 8 ms 15964 KB Output is correct
18 Correct 8 ms 16108 KB Output is correct
19 Correct 3 ms 15964 KB Output is correct
20 Correct 3 ms 15964 KB Output is correct
21 Correct 3 ms 15964 KB Output is correct

Subtask #2
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 887 ms 19036 KB Output is correct
2 Correct 818 ms 20028 KB Output is correct
3 Correct 815 ms 20360 KB Output is correct
4 Correct 823 ms 19528 KB Output is correct
5 Correct 818 ms 20308 KB Output is correct
6 Correct 561 ms 20452 KB Output is correct
7 Correct 545 ms 20560 KB Output is correct
8 Correct 760 ms 20376 KB Output is correct
9 Correct 771 ms 21060 KB Output is correct
10 Correct 744 ms 19400 KB Output is correct
11 Correct 620 ms 20688 KB Output is correct
12 Correct 570 ms 21060 KB Output is correct
13 Correct 548 ms 21332 KB Output is correct

Subtask #3
60.0 / 60.0

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 15960 KB Output is correct
2 Correct 9 ms 15964 KB Output is correct
3 Correct 9 ms 15964 KB Output is correct
4 Correct 10 ms 15964 KB Output is correct
5 Correct 10 ms 16220 KB Output is correct
6 Correct 9 ms 15964 KB Output is correct
7 Correct 9 ms 15964 KB Output is correct
8 Correct 9 ms 15964 KB Output is correct
9 Correct 9 ms 15960 KB Output is correct
10 Correct 14 ms 15964 KB Output is correct
11 Correct 9 ms 15964 KB Output is correct
12 Correct 9 ms 15964 KB Output is correct
13 Correct 8 ms 15964 KB Output is correct
14 Correct 8 ms 15964 KB Output is correct
15 Correct 9 ms 16216 KB Output is correct
16 Correct 8 ms 15964 KB Output is correct
17 Correct 8 ms 15964 KB Output is correct
18 Correct 8 ms 16108 KB Output is correct
19 Correct 3 ms 15964 KB Output is correct
20 Correct 3 ms 15964 KB Output is correct
21 Correct 3 ms 15964 KB Output is correct
22 Correct 887 ms 19036 KB Output is correct
23 Correct 818 ms 20028 KB Output is correct
24 Correct 815 ms 20360 KB Output is correct
25 Correct 823 ms 19528 KB Output is correct
26 Correct 818 ms 20308 KB Output is correct
27 Correct 561 ms 20452 KB Output is correct
28 Correct 545 ms 20560 KB Output is correct
29 Correct 760 ms 20376 KB Output is correct
30 Correct 771 ms 21060 KB Output is correct
31 Correct 744 ms 19400 KB Output is correct
32 Correct 620 ms 20688 KB Output is correct
33 Correct 570 ms 21060 KB Output is correct
34 Correct 548 ms 21332 KB Output is correct
35 Correct 788 ms 19024 KB Output is correct
36 Correct 807 ms 20560 KB Output is correct
37 Correct 832 ms 21368 KB Output is correct
38 Correct 828 ms 21448 KB Output is correct
39 Correct 812 ms 21112 KB Output is correct
40 Correct 854 ms 24592 KB Output is correct
41 Correct 818 ms 24220 KB Output is correct
42 Correct 850 ms 24208 KB Output is correct
43 Correct 823 ms 23496 KB Output is correct
44 Correct 834 ms 23688 KB Output is correct
45 Correct 832 ms 23952 KB Output is correct
46 Correct 827 ms 24628 KB Output is correct
47 Correct 582 ms 23980 KB Output is correct
48 Correct 612 ms 24220 KB Output is correct
49 Correct 798 ms 22984 KB Output is correct
50 Correct 614 ms 23528 KB Output is correct
51 Correct 565 ms 23788 KB Output is correct
52 Correct 657 ms 23752 KB Output is correct