Submission #1217488

#	Time	Username	Problem	Language	Result	Execution time	Memory
1217488		noyancanturk	Two Currencies (JOI23_currencies)	C++20	100 / 100	896 ms	44204 KiB

currencies

#include<bits/stdc++.h>
using namespace std;

#define int int64_t
#define pb push_back

using pii=pair<int,int>;

const int lim=2e5+100;

struct{
  int tree[lim];
  void update(int p,int val){
    while(p<lim){
      tree[p]+=val;
      p+=p&-p;
    }
  }
  void init(){
    for(int i=0;i<lim;i++){
      tree[i]=0;
    }
  }
  int query(int p){
    int ans=0;
    while(p){
      ans+=tree[p];
      p-=p&-p;
    }
    return ans;
  }
  int query(int l,int r){
    if(r<l)return 0;
    return query(r)-query(l-1);
  }
}fw1,fw2;

vector<int>v[lim];
int tin[lim],tt=1;
int sz[lim],par[lim],head[lim];

int sbs(int node){
  for(int i=0;i<v[node].size();i++){
    if(v[node][i]==par[node]){
      swap(v[node][i],v[node].back());
      v[node].pop_back();
      break;
    }
  }
  sz[node]=1;
  for(int j:v[node]){
    par[j]=node;
    sz[node]+=sbs(j);
  }
  return sz[node];
}

void build(int node){
  tin[node]=tt++;
  if(!head[node])head[node]=node;
  if(!v[node].size())return;
  int heavy=v[node][0];
  for(int j:v[node]){
    if(sz[heavy]<sz[j]){
      heavy=j;
    }
  }
  head[heavy]=head[node];
  build(heavy);
  for(int j:v[node]){
    if(j==heavy)continue;
    build(j);
  }
}

pii query(int x,int y){
  int ans1=0,ans2=0;
  while(1){
    if(tin[y]<tin[x])swap(x,y);
    if(head[x]==head[y]){
      ans1+=fw1.query(tin[x]+1,tin[y]);
      ans2+=fw2.query(tin[x]+1,tin[y]);
      break;
    }
    ans1+=fw1.query(tin[head[y]],tin[y]);
    ans2+=fw2.query(tin[head[y]],tin[y]);
    y=par[head[y]];
  }
  return {ans1,ans2};
}

signed main(){
  ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  int n,m,q;
  cin>>n>>m>>q;
  pii edges[n-1];
  for(int i=0;i<n-1;i++){
    int x,y;
    cin>>x>>y;
    edges[i]={x,y};
    v[x].pb(y);
    v[y].pb(x);
  }
  pii guys[m];
  for(int i=0;i<m;i++){
    cin>>guys[i].second>>guys[i].first;
    guys[i].second--;  
  }
  sort(guys,guys+m);
  sbs(1);
  build(1);
  for(int i=0;i<n-1;i++){
    if(edges[i].first!=par[edges[i].second])swap(edges[i].first,edges[i].second);
  }
  for(int i=0;i<m;i++){
    guys[i].second=edges[guys[i].second].second;
  }
  int a[q],b[q],c[q],d[q];
  for(int i=0;i<q;i++){
    cin>>a[i]>>b[i]>>c[i]>>d[i];
  }
  vector<int>mids[m+1];
  int l[q],r[q],ans[q];
  for(int i=0;i<q;i++){
    l[i]=0,r[i]=m;
    ans[i]=-1;
    mids[m>>1].pb(i);
  }
  for(int i=0;i<17;i++){
    fw1.init();
    fw2.init();
    for(int mid=0;mid<m;mid++){
      fw1.update(tin[guys[mid].second],1);
    }
    for(int mid=0;mid<=m;mid++){
      for(int j:mids[mid]){
        auto[ans1,ans2]=query(a[j],b[j]);
        if(ans1<=c[j]&&ans2<=d[j]){
          ans[j]=c[j]-ans1;
          l[j]=mid+1;
          if(l[j]<=r[j])mids[(l[j]+r[j])>>1].pb(j);
        }else if(ans1<=c[j]){
          r[j]=mid-1;
          if(l[j]<=r[j])mids[(l[j]+r[j])>>1].pb(j);
        }else if(ans2<=d[j]){
          l[j]=mid+1;
          if(l[j]<=r[j])mids[(l[j]+r[j])>>1].pb(j);
        }
      }
      mids[mid].clear();
      if(mid!=m){
        fw1.update(tin[guys[mid].second],-1);
        fw2.update(tin[guys[mid].second],guys[mid].first);
      }
    }
  }
  for(int j:ans)cout<<j<<'\n';
}

• Subtask 1: 10 / 10
• Subtask 2: 28 / 28
• Subtask 3: 30 / 30
• Subtask 4: 32 / 32