Submission #655238

#	Time	Username	Problem	Language	Result	Execution time	Memory
655238		d4xn	Regions (IOI09_regions)	C++17	30 / 100	8095 ms	131072 KiB

regions

#pragma GCC optimize ("Ofast")
#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define all(x) x.begin(), x.end()
#define ii pair<int, int>
#define pb push_back
#define vi vector<int>
#define vvi vector<int>
#define vii vector<ii>

const int N = 2e5+5, R1 = 25e3+3, R2 = 5e2+2;

int n, r, q, curr;
int reg[N], sz[N], pre[N], idx[N];
ll ans[R2][R2];
vi adj[N], from[R1];
map<int, int> seg[N*4];

void build(int p=1, int l=0, int r=n-1) {
  if (l == r) {
    seg[p][pre[l]]++;
    return;
  }

  int mid = (l+r)/2;
  build(p*2, l, mid);
  build(p*2+1, mid+1, r);

  for (int h : {p*2, p*2+1}) {
    for (auto &[x, y] : seg[h]) {
      seg[p][x] += y;
    }
  }
}

int query(int a, int b, int c, int p=1, int l=0, int r=n-1) {
  if (r < a || l > b) return 0;
  if (a <= l && r <= b) {
    auto it = seg[p].find(c);
    return (it == seg[p].end() ? 0 : it->second);
  }

  int mid = (l+r)/2;
  int x = query(a, b, c, p*2, l, mid);
  int y = query(a, b, c, p*2+1, mid+1, r);

  return x+y;
}

void dfs(int u) {
  sz[u] = 1;
  pre[curr] = reg[u];
  idx[u] = curr;
  curr++;

  for (int &v : adj[u]) {
    dfs(v);
    sz[u] += sz[v];
  }
}

signed main() {
  ios::sync_with_stdio(false); cin.tie(nullptr);

  cin >> n >> r >> q;

  for (int i = 0; i < n; i++) {
    if (i) {
      int x;
      cin >> x;
      x--;
      adj[x].pb(i);
    }
  
    cin >> reg[i];
    reg[i]--;
    from[reg[i]].pb(i);
  }

  curr = 0;
  dfs(0);
  build();

  if (r <= 500) {
    // precalc all queries
    for (int i = 0; i < r; i++) {
      for (int j = 0; j < r; j++) {
        if (i == j) continue;
        ans[i][j] = 0;
        for (int &u : from[i]) {
          //cerr << i << " " << j << " " << u << " " << query(idx[u], idx[u] + sz[u] - 1, j) << endl;
          ans[i][j] += query(idx[u], idx[u] + sz[u] - 1, j);
        }
        //cerr << ans[i][j] << endl;
      }
    }
  }

  while (q--) {
    int x, y;
    cin >> x >> y;
    x--; y--;
    if (r <= 500) {
      cout << ans[x][y] << endl;
    }
    else {
      ll cnt = 0;
      for (int &u : from[x]) {
        cnt += query(idx[u], idx[u] + sz[u] - 1, y);
      }
      cout << cnt << endl;
    }   
  }
}

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