Submission #874540

#	Time	Username	Problem	Language	Result	Execution time	Memory
874540		1075508020060209tc	Construction of Highway (JOI18_construction)	C++14	100 / 100	292 ms	23664 KiB

construction

//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,avx2,tune=native")
#include <bits/stdc++.h>
using namespace std;
//#define int long long
int bit[100005];
int lowbit(int x){return x&-x;}
int qsum(int pl){
int ret=0;
while(pl){
    ret+=bit[pl];
    pl-=lowbit(pl);
}
return ret;
}
vector<pair<int,int>>uvc;
void updbit(int pl,int v){
uvc.push_back({pl,v});
while(pl<=100000){
    bit[pl]+=v;
    pl+=lowbit(pl);
}
}
void undo(){
int pl=uvc.back().first;int v=uvc.back().second;
v*=-1;
while(pl<=100000){
    bit[pl]+=v;
    pl+=lowbit(pl);
}
uvc.pop_back();
}
int n;
int ar[100005];
vector<int>e[100005];
int dph[100005];
int hd[100005];
int sbsz[100005];
int fa[100005];
set<pair<pair<int,int>,int>>st[100005];
pair<int,int>qar[100005];
void dfssbsz(int nw,int pa){
dph[nw]=dph[pa]+1;
sbsz[nw]=1;
for(int i=0;i<e[nw].size();i++){
    int v=e[nw][i];
    dfssbsz(v,nw);
    sbsz[nw]+=sbsz[v];
}
for(int i=1;i<e[nw].size();i++){
    if(sbsz[e[nw][i]]>sbsz[e[nw][0]]){
        swap(e[nw][i],e[nw][0]);
    }
}
}
void dfshd(int nw,int head){
hd[nw]=head;
if(e[nw].size()){
    dfshd(e[nw][0],head);
}
for(int i=1;i<e[nw].size();i++){
    dfshd(e[nw][i],e[nw][i]);
}
}


void lisanhua(){
vector<int>vc;
for(int i=1;i<=n;i++){
    vc.push_back(ar[i]);
}
sort(vc.begin(),vc.end());
for(int i=1;i<=n;i++){
    ar[i]=1+lower_bound(vc.begin(),vc.end(),ar[i])-vc.begin();
}

}


signed main()
{
    cin.tie(0);
    ios_base::sync_with_stdio(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>ar[i];
    }
    lisanhua();
    for(int i=1;i<=n-1;i++){
        cin>>qar[i].first>>qar[i].second;
        fa[qar[i].second]=qar[i].first;
        e[qar[i].first].push_back(qar[i].second);
    }
    dfssbsz(1,0);
    dfshd(1,1);

    /*for(int i=1;i<=n;i++){
        cout<<hd[i]<<" ";
    }cout<<endl;*/

    st[1].insert({{1,1},ar[1]});
    for(int qqq=1;qqq<=n-1;qqq++){
        int nw=qar[qqq].first;
        vector<pair<pair<int,int>,int>>fvc;
        while(nw!=0){
        vector<pair<pair<int,int>,int>>vc;
        int hdd=hd[nw];
            while(st[hdd].size()){
                auto it=st[hdd].begin();
                pair<pair<int,int>,int>pr=*it;
                if(pr.first.second<=dph[nw]){
                    vc.push_back(pr);
                    st[hdd].erase(it);
                    continue;
                }
                if(pr.first.first<=dph[nw]){
                    int ogr=pr.first.second;
                    pr.first.second=dph[nw];
                    vc.push_back(pr);
                    st[hdd].erase(it);
                    pr={ {dph[nw]+1,ogr} ,pr.second };
                    st[hdd].insert(pr);
                    break;
                }
                break;
            }
            reverse(vc.begin(),vc.end());
            for(int i=0;i<vc.size();i++){
                fvc.push_back(vc[i]);
            }
            nw=fa[hd[nw]];
        }
        int ans=0;
        for(int i=0;i<fvc.size();i++){
            int len=fvc[i].first.second-fvc[i].first.first+1;
            ans+=len*qsum(fvc[i].second-1);
          //  cout<<fvc[i].first.first<<" "<<fvc[i].first.second<<" "<<fvc[i].second<<"\n";
            updbit(fvc[i].second,len);
        }

        for(int i=0;i<fvc.size();i++){
            undo();
        }/*
        for(int i=0;i<=200000;i++){
            bit[i]=0;
        }*/
        cout<<ans<<"\n";
        nw=qar[qqq].second;
        int clr=ar[nw];
        while(nw!=0){
            int r=dph[nw];
            int l=dph[hd[nw]];
            st[hd[nw]].insert({{l,r},clr});
            nw=fa[hd[nw]];
        }


    }



}

Compilation message (stderr)

construction.cpp: In function 'void dfssbsz(int, int)':
construction.cpp:45:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   45 | for(int i=0;i<e[nw].size();i++){
      |             ~^~~~~~~~~~~~~
construction.cpp:50:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 | for(int i=1;i<e[nw].size();i++){
      |             ~^~~~~~~~~~~~~
construction.cpp: In function 'void dfshd(int, int)':
construction.cpp:61:14: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 | for(int i=1;i<e[nw].size();i++){
      |             ~^~~~~~~~~~~~~
construction.cpp: In function 'int main()':
construction.cpp:128:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  128 |             for(int i=0;i<vc.size();i++){
      |                         ~^~~~~~~~~~
construction.cpp:134:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  134 |         for(int i=0;i<fvc.size();i++){
      |                     ~^~~~~~~~~~~
construction.cpp:141:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<std::pair<int, int>, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  141 |         for(int i=0;i<fvc.size();i++){
      |                     ~^~~~~~~~~~~

• Subtask 1: 7 / 7
• Subtask 2: 9 / 9
• Subtask 3: 84 / 84