Submission #1128017

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128017		akamizane	Sails (IOI07_sails)	C++20	100 / 100	135 ms	5160 KiB

sails

#include<bits/stdc++.h>
 
using namespace std;
 

#define debug(...) 40

 
using ll = long long;
using pii = pair<int, int>;
using db = long double;

#define int long long
#define el cout << '\n'
#define fi first
#define se second
#define pb push_back
#define all(x) x.begin(), x.end()
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
#define FOD(i, a, b) for (int i = (a); i >= (b); i--)
#define REP(i, n) for (int i = 0; i < (n); i++)
template <class T1, class T2>bool chmax(T1 &a, T2 b){return a < b ? a = b, 1 : 0;}
template <class T1, class T2>bool chmin(T1 &a, T2 b){return a > b ? a = b, 1 : 0;}

long long rng() {
  static std::mt19937 gen(
      std::chrono::steady_clock::now().time_since_epoch().count());
  return std::uniform_int_distribution<long long>(0, INT64_MAX)(gen);
}

const int maxn = 1e5 + 5;
const int mod = 1e9 + 7;

template <class T> class BIT {
  private:
    int n;
    vector<T> bit;
    vector<T> arr;
 
  public:
    BIT(int n) : n(n), bit(n + 1), arr(n) {}
 
    void set(int k, T val) { add(k, val - arr[k]); }
 
    void add(int k, T val) {
        arr[k] += val;
        k++;
        for (; k <= n; k += k & -k) { bit[k] += val; }
    }
 
    T query(int a, int b) {
        b++;
        T s = 0;
        for (; a > 0; a -= a & -a) { s -= bit[a]; }
        for (; b > 0; b -= b & -b) { s += bit[b]; }
        return s;
    }
};
 
 
template <class T> class RURQBIT {
    private : 
        int n; 
        vector<T> a; 
        BIT<T> b, c; 
    public : 
        RURQBIT(int n) : n(n), a(n + 1), b(n + 2), c(n + 2){}
 
        void build(vector<int> &v){
            for(int i = 1; i <= v.size(); i++){
                a[i] = v[i - 1]; 
                b.set(i, a[i] - a[i - 1]); 
                c.set(i, i * (a[i] - a[i - 1])); 
            }
        }
 
        void add(int l, int r, T v){
            if(l > r) return; 
            b.add(l, v); 
            b.add(r + 1, -v); 
            c.add(l, l * v); 
            c.add(r + 1, -(r + 1) * v); 
        }
 
        T query(int l, int r){
            T rs = (r + 1) * b.query(1, r) - c.query(1, r); 
            T ls = l * b.query(1, l - 1) - c.query(1, l - 1); 
            return rs - ls; 
        }
 
        T query(int l){
            return query(l, l); 
        }
}; 


RURQBIT<int> bit(maxn);

void solve(){
  int n;
  cin >> n;
  vector<pii> a(n);
  for (int i = 0; i < n; i++){
    cin >> a[i].fi >> a[i].se;
  }
  sort(all(a));
  for (int i = 0; i < n; i++){
    auto [h, k] = a[i];
    debug(h, k);
    int val = bit.query(h - k + 1);
    int lo = 1, hi = h;
    while(lo < hi){
      int mid = lo + (hi - lo + 1) / 2;
      if (bit.query(mid) >= val) lo = mid;
      else hi = mid - 1;
    }
    int l1 = lo;
    lo = 1, hi = h;
    while(lo < hi){
      int mid = lo + (hi - lo) / 2;
      if (bit.query(mid) <= val) hi = mid;
      else lo = mid + 1;
    }
    int l2 = hi;
    bit.add(l1 + 1, h, 1);
    bit.add(l2, l2 + k - 1 - (h - l1), 1);
  }
  int ans = 0;
  for (int i = 1; i <= a[n - 1].fi; i++){
    int val = bit.query(i);
    ans += val * (val - 1) / 2;
  }
  cout << ans;
}


int32_t main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  int tests = 1;
  // cin >> tests;
  for (int _ = 1; _ <= tests; _++){
    cerr << "- Case #" << _ << ": \n";
    solve();
    // el;
  }
  return 0;
}

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