oj.uz

Submission #172731

# Submission time Handle Problem Language Result Execution time Memory
172731 2020-01-02T13:26:28 Z AlexLuchianov Pairs (IOI07_pairs) C++14
100 / 100
 633 ms 293916 KB 
#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 = 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;
    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.0 / 6.0

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

Subtask #2
6.0 / 6.0

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

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 590 ms 274296 KB Output is correct
2 Correct 568 ms 274352 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 633 ms 274452 KB Output is correct
2 Correct 552 ms 274424 KB Output is correct
3 Correct 551 ms 274496 KB Output is correct

Subtask #6
7.0 / 7.0

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

Subtask #7
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 1156 KB Output is correct
2 Correct 75 ms 1116 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 1144 KB Output is correct
2 Correct 101 ms 1132 KB Output is correct
3 Correct 103 ms 1144 KB Output is correct
4 Correct 97 ms 1248 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 1700 KB Output is correct
2 Correct 124 ms 1652 KB Output is correct
3 Correct 119 ms 1688 KB Output is correct
4 Correct 117 ms 1656 KB Output is correct

Subtask #10
10.0 / 10.0

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

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 78 ms 632 KB Output is correct
2 Correct 79 ms 732 KB Output is correct
3 Correct 78 ms 716 KB Output is correct

Subtask #12
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 12008 KB Output is correct
2 Correct 172 ms 11896 KB Output is correct
3 Correct 159 ms 12104 KB Output is correct

Subtask #13
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 201 ms 18300 KB Output is correct
2 Correct 253 ms 19164 KB Output is correct
3 Correct 208 ms 19192 KB Output is correct