oj.uz

Submission #650861

# Submission time Handle Problem Language Result Execution time Memory
650861 2022-10-15T21:16:49 Z snpmrnhlol Fire (JOI20_ho_t5) C++17
1 / 100
 900 ms 118808 KB 
#include <bits/stdc++.h>
using namespace std;
//ifstream fin("a.in");
//ofstream fout("a.out");
typedef long long ll;
ll v[200000],l[200000],r[200000],stv[200000],ans[200000],n;
///i misspled square
ll cnt2 = 0,disp = 700000;
class superfenwick{
    ll fen[1000001][2];
private:
    ll query2(ll pos,ll t){
        pos+=disp;
        ll r = 0;
        for(ll i = pos;i > 0;i-=(i&-i))r+=fen[i][t];
        return r;
    }
    void add2(ll pos,ll nr,ll t){
        pos+=disp;
        for(ll i = pos;i <= 1000000;i+=(i&-i))fen[i][t]+=nr;
    }
public:
    ll query(ll l,ll r){
        return (query2(r,0)*r - query2(l - 1,0)*(l - 1)) - query2(r,1) + query2(l - 1,1);
    }
    void add(ll l,ll r,ll nr){
        add2(l,nr,0);
        add2(r + 1,-nr,0);
        add2(l,nr*(l - 1),1);
        add2(r + 1,-nr*r,1);
    }
};
superfenwick triangles,squares;
struct events{
    ll tip,t,l,r,nr;
}v2[2000000];
bool cmp(events a,events b){
    if(a.t == b.t)return a.tip < b.tip;
    return a.t < b.t;
}
void addsqaure(ll l,ll r,ll h,ll nr){
    //cout<<"squaredata:"<<l<<','<<r<<','<<h<<','<<nr<<'\n';
    v2[cnt2++] = {0,0,l,r,nr};
    v2[cnt2++] = {0,h,l,r,-nr};
}
void addtriangle(ll l,ll r,ll nr,ll ydisp = 0){
    if(r == n - 1){
        //cout<<"triangledata:"<<l<<','<<r<<','<<nr<<','<<ydisp<<'\n';
        v2[cnt2++] = {1,ydisp,l - ydisp,r - ydisp,nr};
        v2[cnt2++] = {1,r - l + 1 + ydisp,l - ydisp,r - ydisp,-nr};
    }else{
        addtriangle(l,n - 1,nr);
        addtriangle(r + 1,n - 1,-nr,r - l + 1);
        addsqaure(r + 1,n - 1,r - l + 1,-nr);
    }
}
int main(){
    ll q,i,cnt = 0,j,a,b,c;
    cin>>n>>q;
    for(i = 0;i < n;i++){
        cin>>v[i];
    }
    cnt = -1;
    for(i = 0;i < n;i++){
        while(cnt >= 0 && v[i] > v[stv[cnt]]){
            r[stv[cnt--]] = i;
        }
        stv[++cnt] = i;
    }
    while(cnt-- >= 0){
        r[stv[cnt + 1]] = n;
    }
    cnt = -1;
    for(i = n - 1;i >= 0;i--){
        while(cnt >= 0 && v[i] >= v[stv[cnt]]){
            l[stv[cnt--]] = i;
        }
        stv[++cnt] = i;
    }
    while(cnt-- >= 0){
        l[stv[cnt + 1]] = -200005;
    }
    for(i = 0;i < n;i++){
        l[i]++;r[i]--;
        //fout<<"For i = "<<i<<'\n';
        //fout<<l[i]<<' '<<r[i]<<'\n';
        addtriangle(l[i],r[i],v[i]);
        addtriangle(l[i],i - 1,-v[i]);
        addtriangle(i + 1,r[i],-v[i]);
        //cout<<'\n';
    }
    for(i = 0;i < q;i++){
        cin>>a>>b>>c;
        v2[cnt2++] = {2,a,b - 1,c - 1,i};
    }
    sort(v2,v2 + cnt2,cmp);
    for(i = 0;i < cnt2;i++){
        if(v2[i].tip == 0){
            squares.add(v2[i].l,v2[i].r,v2[i].nr);
        }else if(v2[i].tip == 1){
            triangles.add(v2[i].l,v2[i].r,v2[i].nr);
        }else{
            ans[v2[i].nr] = squares.query(v2[i].l,v2[i].r) + triangles.query(v2[i].l - v2[i].t,v2[i].r - v2[i].t);
        }
    }
    for(i = 0;i < q;i++)cout<<ans[i]<<'\n';
    return 0;
}

Compilation message

ho_t5.cpp: In function 'int main()':
ho_t5.cpp:58:20: warning: unused variable 'j' [-Wunused-variable]
   58 |     ll q,i,cnt = 0,j,a,b,c;
      |                    ^

Subtask #1
1.0 / 1.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 1 ms 564 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 572 KB Output is correct
19 Correct 1 ms 596 KB Output is correct
20 Correct 2 ms 568 KB Output is correct
21 Correct 2 ms 468 KB Output is correct
22 Correct 2 ms 468 KB Output is correct
23 Correct 2 ms 468 KB Output is correct
24 Correct 2 ms 468 KB Output is correct
25 Correct 2 ms 468 KB Output is correct
26 Correct 2 ms 468 KB Output is correct
27 Correct 2 ms 468 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 2 ms 468 KB Output is correct
30 Correct 2 ms 468 KB Output is correct
31 Correct 1 ms 468 KB Output is correct
32 Correct 1 ms 468 KB Output is correct

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 900 ms 118808 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #3
0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 399 ms 118728 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

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

Subtask #5
0 / 80.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 2 ms 596 KB Output is correct
4 Correct 2 ms 492 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 2 ms 468 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 468 KB Output is correct
11 Correct 1 ms 468 KB Output is correct
12 Correct 1 ms 468 KB Output is correct
13 Correct 2 ms 596 KB Output is correct
14 Correct 1 ms 564 KB Output is correct
15 Correct 1 ms 468 KB Output is correct
16 Correct 1 ms 468 KB Output is correct
17 Correct 1 ms 468 KB Output is correct
18 Correct 1 ms 572 KB Output is correct
19 Correct 1 ms 596 KB Output is correct
20 Correct 2 ms 568 KB Output is correct
21 Correct 2 ms 468 KB Output is correct
22 Correct 2 ms 468 KB Output is correct
23 Correct 2 ms 468 KB Output is correct
24 Correct 2 ms 468 KB Output is correct
25 Correct 2 ms 468 KB Output is correct
26 Correct 2 ms 468 KB Output is correct
27 Correct 2 ms 468 KB Output is correct
28 Correct 1 ms 468 KB Output is correct
29 Correct 2 ms 468 KB Output is correct
30 Correct 2 ms 468 KB Output is correct
31 Correct 1 ms 468 KB Output is correct
32 Correct 1 ms 468 KB Output is correct
33 Incorrect 900 ms 118808 KB Output isn't correct
34 Halted 0 ms 0 KB -