Submission #986440

#	Time	Username	Problem	Language	Result	Execution time	Memory
986440		abczz	Sails (IOI07_sails)	C++14	100 / 100	148 ms	9552 KiB

sails

#include <iostream>
#include <array>
#include <algorithm>
#include <queue>
#include <map>
#define ll long long

using namespace std;

ll N = 1e5, n, p, l, r, y, f, cur, z, ul, ur;
array<ll, 2> A[100000];

struct SegTree{
  vector <ll> st{vector <ll>(400000, 0)};
  vector <ll> lazy{vector <ll>(400000, 0)};
  void push(ll id) {
    st[id*2] += lazy[id];
    st[id*2+1] += lazy[id];
    lazy[id*2] += lazy[id];
    lazy[id*2+1] += lazy[id];
    lazy[id] = 0;
  }
  void add(ll id, ll l, ll r, ll ql, ll qr) {
    if (qr < l || r < ql) return;
    else if (ql <= l && r <= qr) {
      ++st[id];
      ++lazy[id];
      return;
    }
    push(id);
    ll mid = (l+r)/2;
    add(id*2, l, mid, ql, qr);
    add(id*2+1, mid+1, r, ql, qr);
    st[id] = max(st[id*2], st[id*2+1]);
  }
  ll query(ll id, ll l, ll r, ll q) {
    if (l == r) return st[id];
    push(id);
    ll mid = (l+r)/2;
    if (q <= mid) return query(id*2, l, mid, q);
    else return query(id*2+1, mid+1, r, q);
  }
  void interval_left(ll id, ll l, ll r, ll w) {
    if (l == r) {
      if (st[id] == w) ul = min(ul, l);
      return;
    }
    push(id);
    ll mid = (l+r)/2;
    if (st[id*2+1] > w) {
      interval_left(id*2+1, mid+1, r, w);
      return;
    }
    else if (st[id*2+1] == w) ul = min(ul, mid+1);
    interval_left(id*2, l, mid, w);
  }
  void interval_right(ll id, ll l, ll r, ll w) {
    if (l == r) {
      if (st[id] == w) ur = max(ur, l);
      return;
    }
    push(id);
    ll mid = (l+r)/2;
    if (st[id*2+1] >= w) interval_right(id*2+1, mid+1, r, w);
    else interval_right(id*2, l, mid, w);
  }
  void solve(ll id, ll l, ll r) {
    if (l == r) {
      f += st[id] * (st[id]-1) / 2;
      return;
    }
    push(id);
    ll mid = (l+r)/2;
    solve(id*2, l, mid);
    solve(id*2+1, mid+1, r);
  }
}ST;
int main() {
  cin >> n;
  for (int i=0; i<n; ++i) {
    cin >> A[i][0] >> A[i][1];
  }
  sort(A, A+n);
  for (int i=0; i<n; ++i) {
    ul = 1e18, ur = -1e18;
    auto w = ST.query(1, 0, N-1, A[i][0]-A[i][1]);
    ST.interval_left(1, 0, N-1, w);
    ST.interval_right(1, 0, N-1, w);
    ur = min(ur, A[i][0]-1);
    if (ur+1 <= A[i][0]-1) ST.add(1, 0, N-1, ur+1, A[i][0]-1);
    ST.add(1, 0, N-1, ul, ul+ur-(A[i][0]-A[i][1]));
  }
  ST.solve(1, 0, N-1);
  cout << f << '\n';
}

• 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