oj.uz

답안 #477001

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
477001 2021-09-29T17:29:15 Z urosk Regions (IOI09_regions) C++14
100 / 100
 5268 ms 78516 KB 
// __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
#define maxr 25005
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[maxr];
ll bsr(ll x,ll i){
    ll l = 0,r = sz(w[x])-1,mid,rez = -1;
    while(l<=r){
        mid = (l+r)/2;
        if(i>=in[w[x][mid]]){
            rez = mid;
            l = mid+1;
        }else r = mid-1;
    }
    return rez;
}
ll bsl(ll x,ll i){
    ll l = 0,r = sz(w[x])-1,mid,rez = -1;
    while(l<=r){
        mid = (l+r)/2;
        if(i<=in[w[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++){
        sort(all(w[i]),cmp);
    }
    ll siz = 1;
    for(ll i = 1;i*i<=n;i++) siz = i+100;
    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) 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;
            }
            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

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.0 / 15.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 5576 KB Output is correct
2 Correct 3 ms 5576 KB Output is correct
3 Correct 5 ms 5576 KB Output is correct
4 Correct 7 ms 5580 KB Output is correct
5 Correct 15 ms 5576 KB Output is correct
6 Correct 28 ms 5704 KB Output is correct
7 Correct 40 ms 5704 KB Output is correct
8 Correct 26 ms 5704 KB Output is correct
9 Correct 42 ms 6088 KB Output is correct
10 Correct 104 ms 6272 KB Output is correct
11 Correct 167 ms 6728 KB Output is correct
12 Correct 134 ms 7240 KB Output is correct
13 Correct 142 ms 7112 KB Output is correct
14 Correct 332 ms 7784 KB Output is correct
15 Correct 300 ms 9812 KB Output is correct

Subtask #2
85.0 / 85.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2095 ms 12244 KB Output is correct
2 Correct 2878 ms 11512 KB Output is correct
3 Correct 3726 ms 14212 KB Output is correct
4 Correct 301 ms 7752 KB Output is correct
5 Correct 477 ms 9160 KB Output is correct
6 Correct 1142 ms 32772 KB Output is correct
7 Correct 1890 ms 33136 KB Output is correct
8 Correct 2729 ms 78516 KB Output is correct
9 Correct 2423 ms 17304 KB Output is correct
10 Correct 5268 ms 21184 KB Output is correct
11 Correct 4806 ms 18484 KB Output is correct
12 Correct 1784 ms 22820 KB Output is correct
13 Correct 2572 ms 22844 KB Output is correct
14 Correct 3316 ms 43680 KB Output is correct
15 Correct 4458 ms 27296 KB Output is correct
16 Correct 3272 ms 30820 KB Output is correct
17 Correct 4257 ms 50096 KB Output is correct