Submission #386171

#	Time	Username	Problem	Language	Result	Execution time	Memory
386171		jeroenodb	Regions (IOI09_regions)	C++14	100 / 100	2633 ms	50088 KiB

regions

#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 2e5,mxR = 2.5e4,  oo = 1e9;
const int c = 448;

int h[mxN], in[mxN], out[mxN], hh[mxN];
vi kids[mxN];
vi sorted[mxR];
struct event {
    int i; bool pos;
    bool operator<(const event& o) const {
        return i< o.i;
    }
};
vector<event> events[mxR];

int cnt = 0;
void dfs(int at) {
    hh[cnt] = h[at];
    events[h[at]].push_back({cnt,true});
    sorted[h[at]].push_back(cnt);
    in[at] = cnt++;

    for(int to: kids[at]) {
        dfs(to);
    }
    out[at] = cnt;
    events[h[at]].push_back({cnt,false});
}

int main() {
    int n,r,q;
    cin >> n >> r >> q;
    for(int i=0;i<n;++i) {
        if(i) {
            int par;
            cin >> par;
            par--;
            kids[par].push_back(i);
        }
        cin >> h[i];
        h[i]--;
    }
    dfs(0);
    for(int i=0;i<r;++i) {
        sort(all(events[i]));
    }
    struct lookuptable {
        vector<ll> ans,ans2;
        int big;
        lookuptable(int b, int rr) {
            ans.resize(rr);
            ans2.resize(rr);
            big = b;
        }
    };
    vector<lookuptable> lookup;
    for(int b=0;b<r;++b) {
        if((int)sorted[b].size()>=c) {
            // precompute answer for all queries of form (i,e_2) or (e_1, i)
            lookuptable l(b,r);
            int overlap = 0;
            auto& mevents = events[b];
            // big group is above other group
            for(int i=0,j=0;i<n;++i) {
                while(j<mevents.size() and mevents[j].i<=i) {
                    if(mevents[j++].pos) {
                        overlap++;
                    } else {
                        overlap--;
                    }
                }
                l.ans[hh[i]]+=overlap;
            }
            // big group is under other group
            // prefix sums?
            vi pref(n+1,0);
            for(int i=1;i<=n;++i) {
                pref[i]+=pref[i-1]+(hh[i-1]==b);
            }
            for(int i=0;i<n;++i) {
                l.ans2[h[i]]+=pref[out[i]] - pref[in[i]];
            }
            lookup.push_back(l);
        }
    }
    while(q--) {
        int a,b; cin >> a >> b; --a,--b;
        if(sorted[a].size()>=c) {
            int l=0,r = lookup.size()-1;
            while(l<r) {
                int mid = (l+r)/2;
                if(lookup[mid].big < a) {
                    l=mid+1;
                } else r = mid;
            }
            cout << lookup[l].ans[b] << endl;
        } else if(sorted[b].size()>=c) {
            int l=0,r = lookup.size()-1;
            while(l<r) {
                int mid = (l+r)/2;
                if(lookup[mid].big < b) {
                    l=mid+1;
                } else r = mid;
            }
            cout << lookup[l].ans2[a] << endl;
        } else {
            auto& es = events[a];
            auto& v = sorted[b];
            ll ans = 0;
            int overlap = 0;
            for(int i=0,j=0; i < v.size();++i) {
                while(j<es.size() and es[j].i<=v[i]) {
                    if(es[j++].pos) {
                        overlap++;
                    } else {
                        overlap--;
                    }
                }
                ans+=overlap;
            }
            cout << ans << endl;
        }
    }
}

Compilation message (stderr)

regions.cpp: In function 'int main()':
regions.cpp:74:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   74 |                 while(j<mevents.size() and mevents[j].i<=i) {
      |                       ~^~~~~~~~~~~~~~~
regions.cpp:120:32: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  120 |             for(int i=0,j=0; i < v.size();++i) {
      |                              ~~^~~~~~~~~~
regions.cpp:121:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<event>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  121 |                 while(j<es.size() and es[j].i<=v[i]) {
      |                       ~^~~~~~~~~~

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