Submission #172729

#	Time	Username	Problem	Language	Result	Execution time	Memory
172729		AlexLuchianov	Pairs (IOI07_pairs)	C++14	80 / 100	605 ms	293956 KiB

pairs

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>

using namespace std;

using ll = long long;
#define MIN(a, b) (((a) < (b)) ? (a) : (b))
#define MAX(a, b) (((a) < (b)) ? (b) : (a))

namespace Subtask1{
  vector<int> v;
  int getsum(int x, int y, int m){
    int result = 0;
    if(y <= m)
      result += v[y];
    else
      result += v[m];
    if(0 < x)
      result -= v[x - 1];
    return result;
  }
  void solve(){
    int n, d, m;
    cin >> n >> d >> m;
    v.resize(1 + m);
    for(int i = 1;i <= n; i++){
      int x;
      cin >> x;
      v[x]++;
    }
    for(int i = 1;i <= m; i++)
      v[i] += v[i - 1];
    ll result = 0;
    for(int i = 1;i <= m; i++)
      if(0 < v[i] - v[i - 1])
        result += (v[i] - v[i - 1]) * getsum(i - d, i + d, m);
    result -= n;
    cout << result / 2 << '\n';
  }
}

namespace Subtask2{
  int const nmax = 200000;
  class FenwickTree{
  private:
    int n;
    vector<int> aib;
  public:
    FenwickTree(int n){
      this->n = n;
      aib.resize(1 + n);
    }
    void update(int x, int val){
      while(x <= n){
        aib[x] += val;
        x += (x ^ (x & (x - 1)));
      }
    }
    int query(int x){
      int result = 0;
      while(0 < x){
        result += aib[x];
        x = (x & (x - 1));
      }
      return result;
    }
  };
  struct Point{
    int x;
    int y;
    bool operator < (Point const &a) const{
      if(x != a.x)
        return x < a.x;
      else
        return y < a.y;
    }
  } v[1 + nmax];

  void solve(){
    int n, d, m;
    cin >> n >> d >> m;
    for(int i = 1;i <= n; i++){
      int x, y;
      cin >> x >> y;
      v[i] = {x + y - 1, x - y + m};
    }
    sort(v + 1, v + n + 1);
    ll result = 0;
    int ptr = 1;
    FenwickTree aib(2 * m);
    for(int i = 1;i <= n; i++){
      aib.update(v[i].y, 1);
      while(v[ptr].x + d < v[i].x){
        aib.update(v[ptr].y, -1);
        ptr++;
      }
      result += aib.query(MIN(2 * m, v[i].y + d)) - aib.query(MAX(0, v[i].y - d - 1));
    }
    cout << result - n;
  }
}
namespace Subtask3{
  int const nmax = 150;
  int v[1 + nmax][1 + nmax][1 + nmax];
  int sum[1 + nmax][1 + nmax][1 + nmax];
  int getsum(int level, int x, int y, int x2, int y2, int m){
    x = MAX(x, 0);
    y = MAX(y, 0);
    x2 = MIN(x2, m);
    y2 = MIN(y2, m);
    return sum[level][x2][y2] - sum[level][x - 1][y2] - sum[level][x2][y - 1] + sum[level][x - 1][y - 1];
  }
  void solve(){
    int n, d, m;
    cin >> n >> d >> m;
    for(int i = 1;i <= n; i++){
      int level, x, y;
      cin >> level >> x >> y;
      int x2 = x + y - 1, y2 = x - y + m;
      v[level][x2][y2]++;
    }
    int lim = 2 * m;
    for(int level = 1;level <= m; level++)
      for(int i = 1;i <= lim; i++)
        for(int j = 1;j <= lim; j++)
          sum[level][i][j] = sum[level][i - 1][j] + sum[level][i][j - 1] - sum[level][i - 1][j - 1] + v[level][i][j];
    ll result = 0;

    for(int level = 1; level <= m; level++){
      for(int i = 1;i <= lim; i++)
        for(int j = 1;j <= lim; j++)
          if(0 < v[level][i][j])
            for(int level2 = 1; level2 <= m; level2++){
              int newd = d - fabs(level2 - level);
              if(0 <= newd) {
                result += v[level][i][j] * getsum(level2, i - newd, j - newd, i + newd, j + newd, lim);
              }
            }
    }
    cout << (result - n) / 2;
  }
}

int main()
{
  int type;
  cin >> type;
  if(type == 1)
    Subtask1::solve();
  else if(type == 2)
    Subtask2::solve();
  else if(type == 3)
    Subtask3::solve();
  return 0;
}

• Subtask 1: 6 / 6
• Subtask 2: 6 / 6
• Subtask 3: 6 / 6
• Subtask 4: 6 / 6
• Subtask 5: 6 / 6
• Subtask 6: 7 / 7
• Subtask 7: 7 / 7
• Subtask 8: 8 / 8
• Subtask 9: 8 / 8
• Subtask 10: 0 / 10
• Subtask 11: 10 / 10
• Subtask 12: 10 / 10
• Subtask 13: 0 / 10