oj.uz

Submission #172732

# Submission time Handle Problem Language Result Execution time Memory
172732 2020-01-02T13:28:57 Z AlexLuchianov Pairs (IOI07_pairs) C++14
100 / 100
 610 ms 293828 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <cassert>

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 = 200;
  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;
    assert(m <= 75);
    for(int i = 1;i <= n; i++){
      int level, x, y;
      cin >> level >> x >> y;
      assert(x <= m && y <= m);
      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.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 256 KB Output is correct
2 Correct 2 ms 256 KB Output is correct

Subtask #2
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 520 ms 293828 KB Output is correct

Subtask #3
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 504 KB Output is correct
2 Correct 38 ms 504 KB Output is correct

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 610 ms 274512 KB Output is correct
2 Correct 574 ms 274480 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 580 ms 274568 KB Output is correct
2 Correct 566 ms 274556 KB Output is correct
3 Correct 556 ms 274552 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 888 KB Output is correct
2 Correct 4 ms 1016 KB Output is correct

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 76 ms 1272 KB Output is correct
2 Correct 74 ms 1272 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 95 ms 1272 KB Output is correct
2 Correct 91 ms 1272 KB Output is correct
3 Correct 91 ms 1244 KB Output is correct
4 Correct 89 ms 1272 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 124 ms 1844 KB Output is correct
2 Correct 119 ms 1912 KB Output is correct
3 Correct 121 ms 1776 KB Output is correct
4 Correct 118 ms 1892 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 12584 KB Output is correct
2 Correct 26 ms 12540 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 77 ms 764 KB Output is correct
2 Correct 81 ms 688 KB Output is correct
3 Correct 78 ms 888 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 12048 KB Output is correct
2 Correct 173 ms 11896 KB Output is correct
3 Correct 159 ms 12152 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 18528 KB Output is correct
2 Correct 242 ms 18724 KB Output is correct
3 Correct 198 ms 18424 KB Output is correct