oj.uz

Submission #991090

# Submission time Handle Problem Language Result Execution time Memory
991090 2024-06-01T09:16:09 Z megatron10 Sails (IOI07_sails) C++17
100 / 100
 36 ms 3676 KB 
#include <bits/stdc++.h>
#define ull uint64_t
#define ll long long int
#define pb push_back
#define mp make_pair
#define pi pair<int, int>
#define vi vector<int>
#define ff first
#define ss second
#define mx5 100005
#define mx52 200005
#define mx6 1000005
#define mod 1000000007
#define smod 998244353
#define nfs                     \
  ios_base::sync_with_stdio(0); \
  cin.tie(0);                   \
  cout.tie(0);
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

void __print(int x) { cerr << x; }
void __print(long x) { cerr << x; }
void __print(long long x) { cerr << x; }
void __print(unsigned x) { cerr << x; }
void __print(unsigned long x) { cerr << x; }
void __print(unsigned long long x) { cerr << x; }
void __print(float x) { cerr << x; }
void __print(double x) { cerr << x; }
void __print(long double x) { cerr << x; }
void __print(char x) { cerr << '\'' << x << '\''; }
void __print(const char *x) { cerr << '\"' << x << '\"'; }
void __print(const string &x) { cerr << '\"' << x << '\"'; }
void __print(bool x) { cerr << (x ? "true" : "false"); }

template <typename T, typename V>
void __print(const pair<T, V> &x)
{
  cerr << '{';
  __print(x.first);
  cerr << ',';
  __print(x.second);
  cerr << '}';
}
template <typename T>
void __print(const T &x)
{
  int f = 0;
  cerr << '{';
  for (auto &i : x)
    cerr << (f++ ? "," : ""), __print(i);
  cerr << "}";
}
void _print() { cerr << "]\n"; }
template <typename T, typename... V>
void _print(T t, V... v)
{
  __print(t);
  if (sizeof...(v))
    cerr << ", ";
  _print(v...);
}
#ifndef ONLINE_JUDGE
#define debug(x...)             \
  cerr << "[" << #x << "] = ["; \
  _print(x)
#else
#define debug(x...)
#endif

template <typename T>
bool MinPlace(T &a, const T &b)
{
  if (a > b)
  {
    a = b;
    return true;
  }
  return false;
}

template <typename T>
bool MaxPlace(T &a, const T &b)
{
  if (a < b)
  {
    a = b;
    return true;
  }
  return false;
}

template <typename S, typename T>
ostream &operator<<(ostream &out, const pair<S, T> &p)
{
  out << "{" << p.ff << ", " << p.ss << "}";
  return out;
}

template <typename T>
ostream &operator<<(ostream &out, const vector<T> &v)
{
  out << "[";
  for (int i = 0; i < (int)v.size(); i++)
  {
    out << v[i];
    if (i != (int)v.size() - 1)
      out << ", ";
  }
  out << "]";
  return out;
}

int main()
{
  nfs;
  int n;
  cin >> n;
  vector<pi> p(n);
  for (int i = 0; i < n; i++)
    cin >> p[i].ff >> p[i].ss;
  sort(p.begin(), p.end());
  set<int> margins{1};
  vi rc(mx5, 0);
  for (const auto &[h, k] : p)
  {
    int low = h - k + 1;
    auto itr = margins.lower_bound(low);
    if (itr == margins.end())
    {
      int m = *(--itr);
      rc[m]++;
      rc[m + k]--;
      if (rc[m] == 0)
        margins.erase(m);
      margins.insert(m + k);
      continue;
    }
    int m = *itr, pm = *(--itr);
    if (m == low)
    {
      rc[low]++;
      rc[h + 1]--;
      if (rc[low] == 0)
        margins.erase(low);
      if (rc[h + 1] == 0)
        margins.erase(h + 1);
      else
        margins.insert(h + 1);
    }
    else
    {
      int down = m - low;
      rc[pm]++;
      rc[pm + down]--;
      rc[m]++;
      rc[h + 1]--;
      if (rc[pm] == 0)
        margins.erase(pm);
      margins.insert(pm + down);
      if (rc[m] == 0)
        margins.erase(m);
      if (rc[h + 1] == 0)
        margins.erase(h + 1);
      else
        margins.insert(h + 1);
    }
  }
  ll ans = 0;
  for (int i = 1; i < mx5; i++)
  {
    rc[i] += rc[i - 1];
    ans += (1ll * rc[i] * (rc[i] - 1)) / 2;
  }
  cout << ans << "\n";
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 600 KB Output is correct
2 Correct 0 ms 860 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

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

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 856 KB Output is correct
2 Correct 9 ms 1252 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 2392 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 18 ms 1628 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 1880 KB Output is correct
2 Correct 23 ms 2908 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 3676 KB Output is correct
2 Correct 21 ms 2140 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 36 ms 2128 KB Output is correct
2 Correct 16 ms 2648 KB Output is correct