Submission #403252

#	Time	Username	Problem	Language	Result	Execution time	Memory
403252		rqi	Regions (IOI09_regions)	C++14	100 / 100	2503 ms	46556 KiB

regions

#include <bits/stdc++.h>
using namespace std;

typedef vector<int> vi;
typedef pair<int, int> pi;
typedef vector<pi> vpi;
typedef long long ll;

#define mp make_pair
#define f first
#define s second
#define pb push_back

#define sz(x) (int)(x).size()
#define all(x) begin(x), end(x)

const int MOD = 1e9+7;

#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;

template<class T> using Tree = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

const int mx = 200005;
const int BLOCK = 350;
const int REGION_mx = 25005;
//const int REGION_mx = 25;
int N, R, Q;

int par[mx];
vi children[mx];
int etind[mx]; //etind of an employee
pi etquery[mx];

int H[mx];
vi region_empls[REGION_mx]; // employees of a region
int sorted_region_ind[REGION_mx];
vpi region_queries[REGION_mx]; //count prefix up to f s times
vi region_updates[REGION_mx]; //update position +1

int pans[mx/BLOCK+5][REGION_mx];
int cans[mx/BLOCK+5][REGION_mx];

int cur_etind = 0;

void dfs(int node){
    etind[node] = ++cur_etind;
    etquery[node].f = cur_etind;
    for(auto u: children[node]){
        dfs(u);
    }
    etquery[node].s = cur_etind;
}

void genETinds(){
    dfs(1);
    assert(cur_etind == N);
}

int csum[mx];

void precomputeAnses(){
    for(int r = 1; r <= R; r++){
        if(sz(region_empls[r]) > BLOCK){
            //do pans, cans[sorted_region_ind]
            for(int i = N; i >= 0; i--){
                csum[i] = 0;
            }
            for(auto &u: region_queries[r]){
                csum[u.f]+=u.s;
            }
            for(int i = N; i >= 0; i--){
                csum[i]+=csum[i+1];
            }
            for(int i = 1; i <= R; i++){
                for(auto &u: region_updates[i]){
                    pans[sorted_region_ind[r]][i]+=csum[u];
                    #warning overflow
                }
            }

            for(int i = 0; i <= N; i++){
                csum[i] = 0;
            }
            for(auto &u: region_updates[r]){
                csum[u]++;
            }
            for(int i = 1; i <= N; i++){
                csum[i]+=csum[i-1];
            }
            for(int i = 1; i <= R; i++){
                for(auto &u: region_queries[i]){
                    cans[sorted_region_ind[r]][i]+=csum[u.f]*u.s;
                    #warning overflow
                }
            }
        }
    }
}

int solveSmall(int r1, int r2){
    // cout << "solving Small" << "\n";
    // for(auto u: region_queries[r1]){
    //     cout << "region_queries: " << u.f << " " << u.s << "\n";
    // }
    // for(auto u: region_updates[r2]){
    //     cout << "region_updates: " <<  u << "\n";
    // }
    int query_ind = 0;
    int update_ind = 0;
    int res = 0;
    int cur = 0;
    while(true){
        int query_num = MOD;
        int update_num = MOD;
        if(query_ind < sz(region_queries[r1])){
            query_num = region_queries[r1][query_ind].f;
        }
        if(update_ind < sz(region_updates[r2])){
            update_num = region_updates[r2][update_ind];
        }
        if(query_num == MOD && update_num == MOD) break;

        //cout << "query, update ind: " << query_ind << " " << update_ind << "\n";
        if(update_num <= query_num){
            
            cur++;
            //cout << "updated" << "\n";
            update_ind++;
        }
        else{
            
            res+=cur*region_queries[r1][query_ind].s;
            //cout << "queried " << res << "\n";
            query_ind++;
        }
    }

    return res;
}

int main(){
    cin.tie(0)->sync_with_stdio(0);
    cin >> N >> R >> Q;
    for(int i = 1; i <= N; i++){
        if(i != 1){
            cin >> par[i];
            children[par[i]].pb(i);
        }
        cin >> H[i];
        region_empls[H[i]].pb(i);
    }

    genETinds();
    // for(int i = 1; i <= N; i++){
    //     cout << "etind: " << i << " " << etind[i] << "\n";
    // }
    vpi sort_by_region_size;
    for(int i = 1; i <= R; i++){
        sort_by_region_size.pb(mp(sz(region_empls[i]), i));
    }
    sort(sort_by_region_size.rbegin(), sort_by_region_size.rend());
    for(int i = 0; i < R; i++){
        sorted_region_ind[sort_by_region_size[i].s] = i;
    }

    for(int i = 1; i <= N; i++){
        region_queries[H[i]].pb(mp(etquery[i].f-1, -1));
        region_queries[H[i]].pb(mp(etquery[i].s, 1));
        region_updates[H[i]].pb(etind[i]);
    }

    for(int i = 1; i <= R; i++){
        sort(all(region_queries[i]));
        sort(all(region_updates[i]));
    }

    precomputeAnses();

    for(int i = 1; i <= Q; i++){
        int r1, r2;
        cin >> r1 >> r2;
        int ans = -1;
        if(sz(region_empls[r1]) > BLOCK){
            ans = pans[sorted_region_ind[r1]][r2];
        }
        else if(sz(region_empls[r2]) > BLOCK){
            ans = cans[sorted_region_ind[r2]][r1];
        }
        else{
            ans = solveSmall(r1, r2);
        }
        cout << ans << "\n";
        cout.flush();
    }
    #warning int overflow
}

Compilation message (stderr)

regions.cpp:78:22: warning: #warning overflow [-Wcpp]
   78 |                     #warning overflow
      |                      ^~~~~~~
regions.cpp:94:22: warning: #warning overflow [-Wcpp]
   94 |                     #warning overflow
      |                      ^~~~~~~
regions.cpp:196:6: warning: #warning int overflow [-Wcpp]
  196 |     #warning int overflow
      |      ^~~~~~~

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