oj.uz

Submission #986440

# Submission time Handle Problem Language Result Execution time Memory
986440 2024-05-20T14:28:02 Z abczz Sails (IOI07_sails) C++14
100 / 100
 148 ms 9552 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6488 KB Output is correct
2 Correct 4 ms 6488 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 6488 KB Output is correct
2 Correct 3 ms 6488 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

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

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6748 KB Output is correct
2 Correct 4 ms 6728 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 6824 KB Output is correct
2 Correct 43 ms 7508 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 51 ms 7768 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 87 ms 7936 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 121 ms 8740 KB Output is correct
2 Correct 107 ms 8788 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 138 ms 9296 KB Output is correct
2 Correct 93 ms 8808 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 148 ms 9552 KB Output is correct
2 Correct 107 ms 9136 KB Output is correct