Submission #1222516

#	Time	Username	Problem	Language	Result	Execution time	Memory
1222516		minhpk	Construction of Highway (JOI18_construction)	C++20	100 / 100	1151 ms	57224 KiB

construction

#include <bits/stdc++.h>
#define int long long
using namespace std;
int a;
int t[1000005];
vector <int> z[1000005];
int sta[1000005];
int fin[1000005];
int tour;
int par[100005][21];
int rev[1000005];
pair<int,int> edge[100005];
vector<int> v;
vector <int> used;
int fwd[1000005];

void dfs(int i,int parent){
    par[i][0]=parent;
    tour++;
    sta[i]=tour;
    rev[tour]=i;

    for (auto p:z[i]){
         dfs(p,i);
    }

    fin[i]=tour;
}

pair<int,int> f[4000005];
pair<int,int> combine(pair<int,int> a, pair<int,int> b){
      if (a.first>b.first){
          return a;
      }else{
          return b;
      }
}

void update(int id,int l,int r,int pos,pair<int,int> val){
    if (l==r){
        f[id]=val;
        return;
    }
    int mid=(l+r)/2;
    if (pos<=mid){
        update(id*2,l,mid,pos,val);
    }else{
        update(id*2+1,mid+1,r,pos,val);
    }
    f[id]=combine(f[id*2],f[id*2+1]);
}

pair<int,int> get(int id,int l,int r,int x,int y){
     if (x>r || y<l){
         return {0LL,0LL};
     }

     if (l>=x && y>=r){
         return f[id];
     }
     int mid=(l+r)/2;
     return combine( get(id*2,l,mid,x,y), get(id*2+1,mid+1,r,x,y) );
}


int bit[1000005];
void reset(){
    for (auto p:used){
        bit[p]=0;
    }
    used.clear();
}
void update(int i,int val){
    i++;
    while (i<=a){
         if (bit[i]==0){
             used.push_back(i);
         }
         bit[i]+=val;

         i+= i&-i;
    }
}

int query(int i){
    i++;
    int res=0;
    while (i>0){
        res+=bit[i];
        i-= i&-i;
    }
    return res;
}
int get(int l,int r){
    if (l>r ){
        return 0;
    }
    return query(r)-query(l-1);
}


signed main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cin >> a;
    for (int i=1;i<=a;i++){
         cin >> t[i];
         v.push_back(t[i]);
    }
    sort(v.begin(),v.end());
    v.erase(unique(v.begin(),v.end()),v.end());

    for (int i=1;i<=a;i++){
         t[i]=lower_bound(v.begin(),v.end(),t[i])-v.begin()+1;
    }
    for (int i=1;i<a;i++){
         int x,y;
         cin >> x >> y;
         z[x].push_back(y);
         edge[i]={x,y};
    }
    dfs(1,0);
    fwd[0]=1;
    for (int i=1;i<=20;i++){
         fwd[i]=fwd[i-1]*2;
    }
    for (int j=1;j<=20;j++){
         for (int i=1;i<=a;i++){
              par[i][j]=par[par[i][j-1]][j-1];
         }
    }
    int cnt=1;
    for (int i=tour;i>=1;i--){
         int u=rev[i];
         pair<int,int> pre={cnt,t[u]};
         update(1,1,tour,sta[u],pre);
         cnt++;
    }

    int q=1;
    while (q<a){
         auto [x,y]=edge[q];
         int res=0;
      //   update(t[y],1);
       //  cout << get(1,1) << "\n";
         int p=x;
         auto [id,preval]=get(1,1,tour,sta[p],fin[p]);
//         if (q==a-1){
//             cout << get(1,1,tour,sta[1],fin[1]).first << get(1,1,tour,sta[1],fin[1]).second << "\n";
//         }
     //    cout << id << " " << preval << "\n";
         while (p>0){
//            if (q==a-1){
//                cout << p << " " << id << " " << preval << "\n";
//            }
            int p1=p;
            int mul=1;
            for (int i=20;i>=0;i--){
                 if (par[p1][i]==0){
                     continue;
                 }
                 pair<int,int> pre=get(1,1,tour,sta[par[p1][i]],fin[par[p1][i]]);
                 if (pre.first==id){
                     mul+=fwd[i];
                     p1=par[p1][i];
                 }
            }

            int val=get(1,preval-1);
           // cout << p1 <<  " " << preval << " " << " ok" << "\n";
            res+=val*mul;
            update(preval,mul);
            p=par[p1][0];
            pair<int,int> pre=get(1,1,tour,sta[p],fin[p]);
            id=pre.first;
            preval=pre.second;

         }

         pair<int,int> pre={q+tour,t[y]};
        // cout << y << " ";
         update(1,1,tour,sta[y],pre);
         cout << res << "\n";
         reset();
         q++;
    }
    return 0;
}

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