Submission #829893

#	Time	Username	Problem	Language	Result	Execution time	Memory
829893		Pajaraja	Two Currencies (JOI23_currencies)	C++17	100 / 100	2624 ms	66428 KiB

currencies

#include <bits/stdc++.h>
#define MAXN 100007
#define MAXL 22
using namespace std;
long long bit[2][4*MAXN],y[MAXN],c[MAXN];
int in[2*MAXN],out[2*MAXN],vreme=1,u[MAXN],v[MAXN],p[MAXL][2*MAXN],f[MAXN],t[MAXN],x[MAXN],ans[MAXN],w,z[MAXN],n,m,q;
vector<int> g[2*MAXN],h[MAXN];
pair<int,int> pi[MAXN];
void upd(int k,int ind,long long s)
{
    while(ind<4*MAXN)
    {
        bit[k][ind]+=s;
        ind+=(ind&-ind);
    }
}
long long parc(int k,int ind)
{
    long long sum=0;
    while(ind)
    {
        sum+=bit[k][ind];
        ind-=(ind&-ind);
    }
    return sum;
}
long long range(int k, int l,int r) {return parc(k,r)-parc(k,l-1);}
void dfs(int s,int f)
{
    p[0][s]=f;
    in[s]=vreme++;
    for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfs(g[s][i],s);
    out[s]=vreme++;
}
bool insub(int a,int b) {return in[a]>=in[b] && out[a]<=out[b];} //jel a u podstablu od b
int lca(int a,int b)
{
    if(insub(a,b)) return b;
    if(insub(b,a)) return a;
    for(int i=MAXL-1;i>=0;i--) if(!insub(a,p[i][b])) b=p[i][b];
    return p[0][b];
}
long long query(int k,int a,int b)
{
    int c=lca(a,b);
    return range(k,in[c],in[a])+range(k,in[c],in[b]);
}
void answerqueries(int l,int r,vector<int> queries)
{
    int s=(l+r)/2;
    while(w<s)
    {
        w++;
        upd(0,in[n+w],c[w]);
        upd(0,out[n+w],-c[w]);
        upd(1,in[n+w],-1);
        upd(1,out[n+w],1);
    }
    while(w>s)
    {
        upd(0,in[n+w],-c[w]);
        upd(0,out[n+w],c[w]);
        upd(1,in[n+w],1);
        upd(1,out[n+w],-1);
        w--;
    }
    vector<int> q1,q2;
    for(int i=0;i<queries.size();i++)
    {
        int ind=queries[i];
        if(query(0,f[ind],t[ind])>y[ind]) q1.push_back(ind);
        else
        {
            q2.push_back(ind);
            ans[ind]=query(1,f[ind],t[ind]);
        }
    }
    if(l==r) return;
    answerqueries(l,s,q1);
    answerqueries(s+1,r,q2);
}
int main()
{
    cin>>n>>m>>q;
    for(int i=1;i<n;i++) cin>>u[i]>>v[i];
    for(int i=1;i<=m;i++) cin>>z[i]>>c[i];
    for(int i=1;i<=m;i++) pi[i]={c[i],z[i]};
    sort(pi+1,pi+m+1);
    for(int i=1;i<=m;i++) {c[i]=pi[i].first; z[i]=pi[i].second;}
    for(int i=1;i<n;i++) h[i].push_back(u[i]);
    for(int i=1;i<=m;i++) h[z[i]].push_back(n+i);
    for(int i=1;i<n;i++) h[i].push_back(v[i]);
    for(int i=1;i<n;i++) for(int j=0;j+1<h[i].size();j++)
    {
        g[h[i][j]].push_back(h[i][j+1]);
        g[h[i][j+1]].push_back(h[i][j]);
    }
    dfs(1,1);
    for(int j=1;j<MAXL;j++) for(int i=1;i<=n+m;i++) p[j][i]=p[j-1][p[j-1][i]];
    for(int i=1;i<=q;i++) cin>>f[i]>>t[i]>>x[i]>>y[i];
    for(int i=1;i<=m;i++)
    {
        upd(1,in[n+i],1);
        upd(1,out[n+i],-1);
    }
    vector<int> queries;
    for(int i=1;i<=q;i++) ans[i]=query(1,f[i],t[i]);
    for(int i=1;i<=q;i++) queries.push_back(i);
    answerqueries(1,m,queries);
    for(int i=1;i<=q;i++) cout<<max(x[i]-ans[i],-1)<<endl;
}

Compilation message (stderr)

currencies.cpp: In function 'void dfs(int, int)':
currencies.cpp:32:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |     for(int i=0;i<g[s].size();i++) if(g[s][i]!=f) dfs(g[s][i],s);
      |                 ~^~~~~~~~~~~~
currencies.cpp: In function 'void answerqueries(int, int, std::vector<int>)':
currencies.cpp:68:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |     for(int i=0;i<queries.size();i++)
      |                 ~^~~~~~~~~~~~~~~
currencies.cpp: In function 'int main()':
currencies.cpp:93:41: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   93 |     for(int i=1;i<n;i++) for(int j=0;j+1<h[i].size();j++)
      |                                      ~~~^~~~~~~~~~~~

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