Submission #490585

#	Time	Username	Problem	Language	Result	Execution time	Memory
490585		CyberSleeper	Regions (IOI09_regions)	C++14	30 / 100	3296 ms	131076 KiB

regions

#include <bits/stdc++.h>
#define fastio      ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL)
#define debug(x)    cout << "Line " << __LINE__ << ", " << #x << " is " << x << endl
#define fi          first
#define se          second
#define mp          make_pair
#define pb          push_back
#define ll          long long
#define ld          long double
#define pii         pair<int, int>
#define pll         pair<ll, ll>
#define ar3         array<int, 3>
#define nl          endl
#define tb          '\t'
#define sp          ' '
using namespace std;

const int MX=200005, MOD=1e9+7, BLOCK=0, INF=1e9+7, INFF=1e18+7;
const ld ERR=1e-7, pi=3.14159265358979323846;

int N, R, Q, op[MX], ed[MX], reg[MX];
vector<int> adj[MX], euler;
vector<pii> rakyat[25005];

void DFS(int p, int x){
    op[x]=euler.size();
    euler.pb(reg[x]);
    for(auto i:adj[x]){
        DFS(x, i);
    }
    ed[x]=euler.size()-1;
}

int main(){
    //fastio;
    cin >> N >> R >> Q >> reg[1];
    for(int i=2, P; i<=N; i++){
        cin >> P >> reg[i];
        adj[P].pb(i);
    }
    DFS(0, 1);
    for(int i=1; i<=N; i++){
        int tmp=reg[i];
        rakyat[tmp].pb({op[i], ed[i]});
    }
    for(int i=0; i<=R; i++)
        sort(rakyat[i].begin(), rakyat[i].end());
    map<pii, int> prec;
    for(int i=1; i<=R; i++){
        if(rakyat[i].size()>BLOCK){
            int cnt=0, idx=0;
            vector<int> sweep(N+1, 0);
            for(auto j:rakyat[i]){
                sweep[j.fi]++;
                sweep[j.se+1]--;
            }
            for(int j=0; j<N; j++){
                cnt+=sweep[j];
                prec[{i, euler[j]}]+=cnt;
            }
        }
    }
    for(int u, v; Q--;){
        cin >> u >> v;
        if(rakyat[u].size()>BLOCK)
            cout << prec[{u, v}] << nl;
        else{
            int ans=0;
            for(auto i:rakyat[v])
                ans+=upper_bound(rakyat[u].begin(), rakyat[u].end(), mp(i.fi, -INF))-lower_bound(rakyat[u].begin(), rakyat[u].end(), mp(i.se, INF));
            cout << ans << nl;
        }
    }
}

Compilation message (stderr)

regions.cpp:18:62: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   18 | const int MX=200005, MOD=1e9+7, BLOCK=0, INF=1e9+7, INFF=1e18+7;
      |                                                          ~~~~^~
regions.cpp: In function 'int main()':
regions.cpp:51:24: warning: unused variable 'idx' [-Wunused-variable]
   51 |             int cnt=0, idx=0;
      |                        ^~~

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