Submission #895381

#	Time	Username	Problem	Language	Result	Execution time	Memory
895381		Ahmed57	Regions (IOI09_regions)	C++17	100 / 100	3241 ms	121336 KiB

regions

#include <bits/stdc++.h>
 
using namespace std;
long long frq[25001],a3[25001];
int xd[25001],x,p,lol[200001],j,a,b;
const int B = 900;
const int L = (200000+B-1)/B;
vector<int> adj[200001];
vector<int> bi;
int rev[25001];
long long cs1[25001][L],cs2[25001][L];
int timer = 0;
vector<pair<int,int>> rngs[25001];
long long idx,all;
void dfs(int i){
    frq[lol[i]]++;
    a3[lol[i]]++;
    timer++;
    int sav = timer;
    for(j = 0;j<bi.size();j++){
        //cout<<i<<" "<<qu[i][j].first<<" "<<qu[i][j].second<<endl;
        cs1[lol[i]][j]+=frq[bi[j]];
        cs2[lol[i]][j]-=a3[bi[j]];
    }
    for(int w = 0;w<adj[i].size();w++){
        dfs(adj[i][w]);
    }
    for(j = 0;j<bi.size();j++){
        cs2[lol[i]][j]+=a3[bi[j]];
    }
    rngs[lol[i]].push_back({timer,sav});
    frq[lol[i]]--;
}
int bit[200001];
void add(int x,int v){
    while(x<=timer){
        bit[x]+=v;
        x+=(x&-x);
    }
}
int sum(int x){
    int su = 0;
    while(x>=1){
        su+=bit[x];
        x-=(x&-x);
    }
    return su;
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);
    //freopen("input.txt","r",stdin);
    //freopen("outout.txt","w",stdout);
    int n,r,q;cin>>n>>r>>q;
    cin>>x;xd[x]++;
    lol[1] = x;
    for(int i = 2;i<=n;i++){
        cin>>p>>x;
        xd[x]++;
        lol[i] = x;
        adj[p].push_back(i);
    }
    for(int i = 1;i<=r;i++){
        if(xd[i]>=B){
            rev[i] = bi.size();
            bi.push_back(i);
        }
    }
    dfs(1);
    for(int i = 1;i<=r;i++){
        sort(rngs[i].begin(),rngs[i].end());
    }
    for(int i = 1;i<=q;i++){
        cin>>a>>b;
        if(xd[b]<B&&xd[a]>=B){
            cout<<cs1[b][rev[a]]<<endl;
        }else if(xd[b]>=B){
            cout<<cs2[a][rev[b]]<<endl;
        }else{
            idx = 0 ;all = 0;
            for(j = 0;j<rngs[a].size();j++){
                while(idx<rngs[b].size()&&rngs[b][idx].first<=rngs[a][j].first){
                    add(rngs[b][idx++].second,1);
                }
                all+=sum(timer)-sum(rngs[a][j].second-1);
            }while(idx>0){
                add(rngs[b][--idx].second,-1);
            }
            cout<<all<<endl;
        }
    }
    return 0;
}

Compilation message (stderr)

regions.cpp: In function 'void dfs(int)':
regions.cpp:20:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   20 |     for(j = 0;j<bi.size();j++){
      |               ~^~~~~~~~~~
regions.cpp:25:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   25 |     for(int w = 0;w<adj[i].size();w++){
      |                   ~^~~~~~~~~~~~~~
regions.cpp:28:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   28 |     for(j = 0;j<bi.size();j++){
      |               ~^~~~~~~~~~
regions.cpp: In function 'int main()':
regions.cpp:80:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   80 |             for(j = 0;j<rngs[a].size();j++){
      |                       ~^~~~~~~~~~~~~~~
regions.cpp:81:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |                 while(idx<rngs[b].size()&&rngs[b][idx].first<=rngs[a][j].first){
      |                       ~~~^~~~~~~~~~~~~~~

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