oj.uz

Submission #172723

# Submission time Handle Problem Language Result Execution time Memory
172723 2020-01-02T13:07:36 Z AlexLuchianov Pairs (IOI07_pairs) C++14
60 / 100
 593 ms 294036 KB 
#include <iostream>
#include <vector>
#include <algorithm>

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{
  void solve(){
    return ;
  }
}

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 516 ms 294036 KB Output is correct

Subtask #3
6.0 / 6.0

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

Subtask #4
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 593 ms 275320 KB Output is correct
2 Correct 565 ms 275236 KB Output is correct

Subtask #5
6.0 / 6.0

# Verdict Execution time Memory Grader output
1 Correct 557 ms 275268 KB Output is correct
2 Correct 589 ms 275264 KB Output is correct
3 Correct 556 ms 275256 KB Output is correct

Subtask #6
7.0 / 7.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 1680 KB Output is correct
2 Correct 74 ms 1784 KB Output is correct

Subtask #8
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 92 ms 1912 KB Output is correct
2 Correct 91 ms 1812 KB Output is correct
3 Correct 91 ms 1912 KB Output is correct
4 Correct 90 ms 1912 KB Output is correct

Subtask #9
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 123 ms 2860 KB Output is correct
2 Correct 121 ms 2824 KB Output is correct
3 Correct 118 ms 2808 KB Output is correct
4 Correct 119 ms 2720 KB Output is correct

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 380 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 252 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #12
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #13
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 376 KB Output isn't correct
2 Halted 0 ms 0 KB -