Submission #476993

#	Time	Username	Problem	Language	Result	Execution time	Memory
476993		urosk	Regions (IOI09_regions)	C++14	95 / 100	5413 ms	131076 KiB

regions

// __builtin_popcount(x) broj bitova
// __builtin_popcountll(x) long long
#define here cerr<<"---------------------------\n"
#include "bits/stdc++.h"
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/assoc_container.hpp>
#define ld double
#define ll long long
#define ull unsigned long long
#define llinf 100000000000000000LL // 10^17
#define iinf 2000000000 // 2*10^9
#define pb push_back
#define popb pop_back
#define fi first
#define sc second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pld pair<ld,ld>
#define sz(a) int(a.size())
#define all(a) a.begin(),a.end()
#define rall(a) a.begin(),a.end(),greater<int>()
#define getunique(v) {sort(all(v)); v.erase(unique(all(v)), v.end());}

using namespace std;
using namespace __gnu_pbds;

typedef tree<int,null_type,less<int>,rb_tree_tag,tree_order_statistics_node_update> ordered_set;

void setIO(string inoutname)
{
	freopen((inoutname+".in").c_str(),"r",stdin);
    	freopen((inoutname+".out").c_str(),"w",stdout);
}
#define mod 1
ll gcd(ll a, ll b)
{
   if(b==0) return a;
   if(a==0) return b;
   if(a>=b)  return gcd(a%b,b);
   return  gcd(a,b%a);
}
ll lcm(ll a,ll b){
   return (a/gcd(a,b))*b;
}
ll add(ll a,ll b){
	a+=b;
	a+=mod;
	if(a>=mod) a%=mod;
	return a;
}
ll mul(ll a,ll b){return(a*b)%mod;}
#define maxn 200005
ll n,r,q;
ll a[maxn];
ll b[maxn];
ll in[maxn],out[maxn];
ll cnt[maxn];
vector<ll> g[maxn];
ll ti = 1;
void dfs(ll u){
    in[u] = ti;
    b[ti] = a[u];
    ti++;
    for(ll v : g[u]){
        dfs(v);
    }
    out[u] = ti-1;
}
bool in_t(ll v,ll u){
    return in[u]<=in[v]&&out[u]>=out[v];
}
bool cmp(ll x,ll y){return in[x]<in[y];}
map<pll,ll> pre;
vector<ll> w[maxn];
vector<ll> wt[maxn];
vector<pll> f;
ll bsr(ll x,ll i){
    ll l = 0,r = sz(wt[x])-1,mid,rez = -1;
    while(l<=r){
        mid = (l+r)/2;
        if(i>=wt[x][mid]){
            rez = mid;
            l = mid+1;
        }else r = mid-1;
    }
    return rez;
}
ll bsl(ll x,ll i){
    ll l = 0,r = sz(wt[x])-1,mid,rez = -1;
    while(l<=r){
        mid = (l+r)/2;
        if(i<=wt[x][mid]){
            rez = mid;
            r = mid-1;
        }else l = mid+1;;
    }
    return rez;
}
void tc(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
    cin >> n >> r >> q;
    cin >> a[1];
    w[a[1]].pb(1);
    for(ll i = 2;i<=n;i++){
        ll x;
        cin >> x >> a[i];
        w[a[i]].pb(i);
        g[x].pb(i);
    }
    dfs(1);
    for(ll i = 1;i<=r;i++){
        for(ll j : w[i]){
            wt[i].pb(in[j]);
        }
        sort(all(wt[i]));
    }
    ll siz = 1;
    for(ll i = 1;i*i<=n;i++) siz = i+30;
    for(ll i = 1;i<=r;i++){
        if(sz(w[i])<siz) continue;
        fill(cnt,cnt+n+2,0);
        for(ll j : w[i]){
            cnt[in[j]]++;
            cnt[out[j]+1]--;
        }
        for(ll j = 1;j<ti;j++){
            cnt[j]+=cnt[j-1];
            pre[{i,b[j]}]+=cnt[j];
        }
    }
    /*here;
    for(ll j = 1;j<=r;j++){
            for(ll i : wt[j]) cerr<<i<< " ";
            cerr<<endl;
    }
    here;*/
    while(q--){
        ll r1,r2;
        cin >> r1 >> r2;
        if(sz(w[r1])>=siz||pre.count({r1,r2})) cout<<pre[{r1,r2}]<<endl;
        else{
            ll ans = 0;
            //cerr<<"R2: "<<r2<<endl;
            for(ll i : w[r1]){
                ll l = in[i],r = out[i];
                ll br = bsr(r2,r);
                ll bl = bsl(r2,l);
                //cerr<<"AAA"<<endl;
                //cerr<<l<< " "<<r<<endl;
                //cerr<<bl<< " "<<br<<endl;
                if(bl==-1) continue;
                if(br==-1) continue;
                if(bl>br) continue;
                //cerr<<bl<< " "<<br<<" "<<br-bl<<endl;
                ans+=br-bl+1;
            }
            pre[{r1,r2}] = ans;
            cout<<ans<<endl;
        }
    }
}
int main(){
	ios_base::sync_with_stdio(false);cerr.tie(0);cout.tie(0);cin.tie(0);
	//setIO("lol");
	int t; t = 1;
	while(t--){
		tc();
	}
	return 0;
}

Compilation message (stderr)

regions.cpp: In function 'void setIO(std::string)':
regions.cpp:31:9: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   31 |  freopen((inoutname+".in").c_str(),"r",stdin);
      |  ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
regions.cpp:32:13: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   32 |      freopen((inoutname+".out").c_str(),"w",stdout);
      |      ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 15 / 15
• Subtask 2: 80 / 85