Submission #991087

#	Time	Username	Problem	Language	Result	Execution time	Memory
991087		megatron10	Sails (IOI07_sails)	C++17	0 / 100	1101 ms	5968 KiB

sails

#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;
}

template <typename T = ll>
class BIT
{
  int n;
  vector<T> v;

public:
  BIT(int n) : n(n)
  {
    v.resize(n + 1, 0);
  }

  void inc(int pos, T delta = 1)
  {
    for (int i = pos; i <= n; i += i & (-i))
      v[i] += delta;
  }

  void dec(int pos, T delta = 1)
  {
    inc(pos, -delta);
  }

  T qry(int r)
  {
    if (r <= 0 || r > n)
      return -1;
    T ret = 0;
    for (int i = r; i; i = i & (i - 1))
      ret += v[i];
    return ret;
  }

  T rangeQry(int l, int r)
  {
    return qry(r) - qry(l - 1);
  }

  void upd(int pos, T val)
  {
    inc(pos, val - pointQry(pos));
  }

  T pointQry(int pos)
  {
    return qry(pos) - qry(pos - 1);
  }
};

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{0, 1};
  BIT<int> rc(mx5 - 1);
  for (auto [h, k] : p)
  {
    int low = h - k + 1;
    auto itr = margins.lower_bound(low);
    if (itr == margins.end())
    {
      int m = *(--itr);
      rc.inc(m);
      rc.dec(m + k);
      margins.insert(m + k);
      if (rc.qry(m) == rc.qry(m - 1))
        margins.erase(m);
      debug(h, k, margins);
      continue;
    }
    int m = *itr, pm = *(--itr);
    if (m == low)
    {
      rc.inc(low);
      rc.dec(h + 1);
      if (rc.qry(low - 1) == rc.qry(low))
        margins.erase(low);
    }
    else
    {
      int down = m - low;
      rc.inc(pm);
      rc.dec(pm + down);
      rc.inc(m);
      rc.dec(h + 1);
      margins.insert(pm + down);
      if (rc.qry(pm) == rc.qry(pm - 1))
        margins.erase(pm);
      if (rc.qry(m) == rc.qry(m - 1))
        margins.erase(m);
    }
    debug(h, k, margins);
  }
  ll ans = 0;
  for (int i = 1; i < mx5; i++)
  {
    int c = rc.qry(i);
    ans += (1ll * c * (c - 1)) / 2;
  }
  cout << ans << "\n";
}

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