oj.uz

Submission #1004634

# Submission time Handle Problem Language Result Execution time Memory
1004634 2024-06-21T11:01:20 Z Mardonbekhazratov Regions (IOI09_regions) C++17
23 / 100
 8000 ms 60104 KB 
#include<bits/stdc++.h>
using namespace std;

struct mergeSortTree{
    int N,n;
    vector<vector<int>>tree;

    void build(int v,int l,int r,vector<int>&a){
        if(l>=n) return;
        if(r-l==1){
            tree[v]={a[l]};
            return;
        }

        int mid=(l+r)/2;
        build(v<<1,l,mid,a);
        build(v<<1|1,mid,r,a);
        merge(tree[v<<1].begin(),tree[v<<1].end(),tree[v<<1|1].begin(),tree[v<<1|1].end(),back_inserter(tree[v]));
    }

    mergeSortTree(vector<int>&a){
        n=(int)a.size();
        N=1;
        while(N<n) N<<=1;
        tree.resize(2*N);
        build(1,0,N,a);
    }

    // void update(int v,int l,int r,int id,int x){
    //     cout<<v;
    //     if(r-l==1){
    //         tree[v]+=x;
    //         return;
    //     }

    //     int mid=(l+r)/2;

    //     if(mid>id) update(v<<1,l,mid,id,x);
    //     else update(v<<1|1,mid,r,id,x);

    //     tree[v]=tree[v<<1]+tree[v<<1|1];
    // }

    // void update(int id,int x){
    //     return update(1,0,N,id,x);
    // }

    int get(int v,int l,int r,int ql,int qr,int x){
        if(ql>=r || l>=qr) return 0;
        if(l>=ql && qr>=r) return lower_bound(tree[v].begin(),tree[v].end(),x+1)-lower_bound(tree[v].begin(),tree[v].end(),x);
        
        int mid=(l+r)/2;

        return get(v<<1,l,mid,ql,qr,x)+get(v<<1|1,mid,r,ql,qr,x);
    }

    int get(int l,int r,int x){
        return get(1,0,N,l,r,x);
    }
};

int n,r,q,timer = 0;
vector<int>h,tin,tout,b;
vector<vector<int>>v,a,dp;

void dfs(int x){
    tin[x]=timer++;
    b.push_back(h[x]);
    for(int z:v[x]){
        dfs(z);
    }
    tout[x]=timer;
}

signed main(){
    cin>>n>>r>>q;
    h.resize(n+1);
    a.resize(r+1);
    cin>>h[1];
    v.assign(n+1,vector<int>(0));
    // dp.assign(r+1,vector<int>(r+1,-1));
    for(int i=2,x;i<=n;i++){
        cin>>x>>h[i];
        v[x].push_back(i);
    }
    for(int i=1;i<=n;i++){
        a[h[i]].push_back(i);
    }
    tin.resize(n+1);
    tout.resize(n+1);
    dfs(1);
    mergeSortTree S(b);
    vector<int>r_id(r+1,-1);
    int cur=-1;
    vector<vector<int>>calc;
    for(int i=1;i<=r;i++){
        if(a[i].size()>=sqrt(n)){
            r_id[i]=++cur;
            calc.push_back(vector<int>(r+1));
            for(int j=1;j<=n;j++){
                int ans=0;
                for(int x:a[i]){
                    ans+=S.get(tin[x],tout[x],j);
                }
                calc[cur][j]=ans;
            }
        }
    }
    while(q--){
        int r1,r2;
        cin>>r1>>r2;
        if(r_id[r1]!=-1){
            cout<<calc[r_id[r1]][r2]<<'\n';
        }
        else{
            int ans=0;
            for(int x:a[r1]){
                ans+=S.get(tin[x],tout[x],r2);
            }
            cout<<ans<<'\n';
        }
    }
}

Subtask #1
13.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 2 ms 344 KB Output is correct
4 Correct 2 ms 344 KB Output is correct
5 Correct 5 ms 344 KB Output is correct
6 Correct 12 ms 600 KB Output is correct
7 Correct 20 ms 600 KB Output is correct
8 Correct 25 ms 856 KB Output is correct
9 Correct 67 ms 1880 KB Output is correct
10 Correct 91 ms 2904 KB Output is correct
11 Correct 258 ms 4012 KB Output is correct
12 Correct 371 ms 5976 KB Output is correct
13 Correct 306 ms 6232 KB Output is correct
14 Runtime error 423 ms 14856 KB Execution killed with signal 6
15 Runtime error 2141 ms 25080 KB Execution killed with signal 6

Subtask #2
10.0 / 85.0

# Verdict Execution time Memory Grader output
1 Execution timed out 8045 ms 21704 KB Time limit exceeded
2 Execution timed out 8020 ms 21448 KB Time limit exceeded
3 Execution timed out 8038 ms 25472 KB Time limit exceeded
4 Correct 766 ms 7708 KB Output is correct
5 Correct 1134 ms 11656 KB Output is correct
6 Runtime error 4323 ms 27212 KB Execution killed with signal 6
7 Runtime error 2063 ms 41060 KB Execution killed with signal 11
8 Execution timed out 8069 ms 28952 KB Time limit exceeded
9 Execution timed out 8042 ms 44228 KB Time limit exceeded
10 Execution timed out 8029 ms 51160 KB Time limit exceeded
11 Execution timed out 8051 ms 51608 KB Time limit exceeded
12 Execution timed out 8013 ms 51660 KB Time limit exceeded
13 Execution timed out 8045 ms 51656 KB Time limit exceeded
14 Execution timed out 8016 ms 53068 KB Time limit exceeded
15 Execution timed out 8023 ms 56228 KB Time limit exceeded
16 Execution timed out 8048 ms 60104 KB Time limit exceeded
17 Execution timed out 8018 ms 59084 KB Time limit exceeded