oj.uz

Submission #650859

# Submission time Handle Problem Language Result Execution time Memory
650859 2022-10-15T21:08:39 Z snpmrnhlol Fire (JOI20_ho_t5) C++17
0 / 100
 701 ms 62068 KB 
#include <bits/stdc++.h>
using namespace std;
int v[200000],l[200000],r[200000],stv[200000],ans[200000],n;
///i misspled square
int cnt2 = 0,disp = 700000;
class superfenwick{
    int fen[1000001][2];
private:
    int query2(int pos,int t){
        pos+=disp;
        int r = 0;
        for(int i = pos;i > 0;i-=(i&-i))r+=fen[i][t];
        return r;
    }
    void add2(int pos,int nr,int t){
        pos+=disp;
        for(int i = pos;i <= 1000000;i+=(i&-i))fen[i][t]+=nr;
    }
public:
    int query(int l,int r){
        return (query2(r,0)*r - query2(l - 1,0)*(l - 1)) - query2(r,1) + query2(l - 1,1);
    }
    void add(int l,int r,int 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{
    int 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(int l,int r,int h,int nr){
    //cout<<"squaredata:"<<l<<','<<r<<','<<h<<','<<nr<<'\n';
    v2[cnt2++] = {0,0,l,r,nr};
    v2[cnt2++] = {0,h,l,r,-nr};
}
void addtriangle(int l,int r,int nr,int 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(){
    int 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]--;
        //cout<<"For i = "<<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:55:21: warning: unused variable 'j' [-Wunused-variable]
   55 |     int q,i,cnt = 0,j,a,b,c;
      |                     ^

Subtask #1
0 / 1.0

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

Subtask #2
0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Incorrect 701 ms 61788 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 367 ms 61996 KB Output isn't correct
3 Halted 0 ms 0 KB -

Subtask #4
0 / 6.0

# Verdict Execution time Memory Grader output
1 Incorrect 272 ms 62068 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 Incorrect 1 ms 468 KB Output isn't correct
3 Halted 0 ms 0 KB -