Submission #758277

#	Time	Username	Problem	Language	Result	Execution time	Memory
758277		groshi	Fire (JOI20_ho_t5)	C++17	100 / 100	929 ms	99316 KiB

ho_t5

#include<iostream>
#include<vector>
#define int long long
using namespace std;
int t[800000];
int lewo[800000];
int prawo[800000];
pair<int,int> drzewo[4000000][2];
int pot=1;
int wynik[800000];
vector<pair<int,pair<int,int> > > zapp[800000];
vector<pair<int,int> > zmiana[800000];
void add(int x,int l,int r,int a,int b,int co,int gdzie)
{
    if(b<l || a>r)
        return;
    //cout<<"jestem w "<<x<<"\n";
    if(a<=l && r<=b)
    {
        drzewo[x][gdzie].second+=co;
        return;
    }
    int mid=(l+r)/2;
    add(x*2,l,mid,a,b,co,gdzie);
    add(x*2+1,mid+1,r,a,b,co,gdzie);
    drzewo[x][gdzie].first=drzewo[x*2][gdzie].first+drzewo[x*2][gdzie].second*(mid-l+1)+drzewo[x*2+1][gdzie].first+drzewo[x*2+1][gdzie].second*(r-mid);
}
int zap(int x,int l,int r,int a,int b,int gdzie)
{
    if(a>r || b<l)
        return 0;
    if(a<=l && r<=b)
        return drzewo[x][gdzie].first+drzewo[x][gdzie].second*(r-l+1);
    int mid=(l+r)/2;
    return zap(x*2,l,mid,a,b,gdzie)+zap(x*2+1,mid+1,r,a,b,gdzie)+drzewo[x][gdzie].second*(min(b,r)-max(a,l)+1);
}
void dodaj(int x,int l,int r)
{
    //cout<<x<<": "<<l<<" "<<r<<"\n";
    zmiana[0].push_back({x,t[x]});
    zmiana[l].push_back({x,-t[x]});
    zmiana[r].push_back({r+x,-t[x]});
    zmiana[l+r].push_back({x+r,t[x]});
}
int32_t main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int n,m;
    cin>>n>>m;
    while(pot<=800000)
        pot*=2;
    pot--;
    for(int i=1;i<=n;i++)
        cin>>t[i];
    vector<int> Q;
    t[0]=1e18;
    t[n+1]=1e18;
    Q.push_back(0);
    for(int i=1;i<=n;i++)
    {
        while(Q.size() && t[Q.back()]<=t[i])
            Q.pop_back();
        lewo[i]=Q.back();
        Q.push_back(i);
    }
    Q.clear();
    Q.push_back(n+1);
    for(int i=n;i>=1;i--)
    {
        while(Q.size() && t[Q.back()]<t[i])
            Q.pop_back();
        prawo[i]=Q.back();
        Q.push_back(i);
    }
    for(int i=1;i<=n;i++)
    {
        if(lewo[i]==0)
            lewo[i]=n+1;
        else lewo[i]=i-lewo[i];
        prawo[i]-=i;
        dodaj(i,lewo[i],prawo[i]);
    }
    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        cin>>x>>y>>z;
        zapp[x].push_back({i,{y,z}});
    }
    int stala=400000;
    for(int i=0;i<=n;i++)
    {
        for(int j=0;j<zmiana[i].size();j++)
        {
            int gdzie=zmiana[i][j].first;
            int ile=zmiana[i][j].second;
            add(1,pot+1,pot*2+1,gdzie+pot,pot*2+1,ile,0);
            add(1,pot+1,pot*2+1,stala+pot+1+gdzie,pot*2+1,-ile,1);
        }
        for(int j=0;j<zapp[i].size();j++)
        {
            int x=zapp[i][j].first;
            int l=zapp[i][j].second.first;
            int r=zapp[i][j].second.second;
            wynik[x]=zap(1,pot+1,pot*2+1,l+pot,r+pot,0)+zap(1,pot+1,pot*2+1,stala+l+pot,stala+r+pot,1);
        }
        stala--;
    }
    for(int i=1;i<=m;i++)
        cout<<wynik[i]<<"\n";
    return 0;
}

Compilation message (stderr)

ho_t5.cpp: In function 'int32_t main()':
ho_t5.cpp:94:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   94 |         for(int j=0;j<zmiana[i].size();j++)
      |                     ~^~~~~~~~~~~~~~~~~
ho_t5.cpp:101:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |         for(int j=0;j<zapp[i].size();j++)
      |                     ~^~~~~~~~~~~~~~~

• Subtask 1: 1 / 1
• Subtask 2: 6 / 6
• Subtask 3: 7 / 7
• Subtask 4: 6 / 6
• Subtask 5: 80 / 80