Submission #1313084

#	Time	Username	Problem	Language	Result	Execution time	Memory
1313084		comgaTramAnh	Sails (IOI07_sails)	C++20	100 / 100	410 ms	14820 KiB

sails

#include <bits/stdc++.h> 
using namespace std;
int main() {
  int n; 
  cin >> n;
  vector <pair <int, int>> a(n);
  vector <vector <int>> save(100005); 
  for (int i = 0; i < n; i++) {
    cin >> a[i].first >> a[i].second; 
    save[a[i].first].push_back(i);
  }
  struct itnode {
    int maxValue = -1000000007, minValue = 1000000007, moreValue = 0;
    long long sum = 0LL;  
  };
  vector <itnode> it(4 * 100005); 
  function <void(int, int, int)> lazyUpdate = [&](int index, int L, int R) {
    if (L < R) {
      int mid = (L + R) / 2; 
      it[2 * index].moreValue += it[index].moreValue;
      it[2 * index].maxValue += it[index].moreValue;
      it[2 * index].minValue += it[index].moreValue;
      it[2 * index].sum += (long long) (mid - L + 1) * it[index].moreValue; 
      it[2 * index + 1].moreValue += it[index].moreValue;
      it[2 * index + 1].maxValue += it[index].moreValue;
      it[2 * index + 1].minValue += it[index].moreValue;
      it[2 * index + 1].sum += (long long) (R - mid) * it[index].moreValue; 
    }
    it[index].moreValue = 0; 
  };
  function <void(int, int, int, int, int)> update = [&](int index, int L, int R, int l, int r) {
    lazyUpdate(index, L, R); 
    if (l > R || L > r) {
      return; 
    }
    if (l <= L && R <= r) {
      it[index].moreValue++;
      it[index].maxValue++;
      it[index].minValue++;
      it[index].sum += R - L + 1; 
      lazyUpdate(index, L, R); 
      return; 
    }
    int mid = (L + R) / 2; 
    update(2 * index, L, mid, l, r); 
    update(2 * index + 1, mid + 1, R, l, r); 
    it[index].maxValue = max(it[2 * index].maxValue, it[2 * index + 1].maxValue);
    it[index].minValue = min(it[2 * index].minValue, it[2 * index + 1].minValue);
    it[index].sum = it[2 * index].sum + it[2 * index + 1].sum; 
  };
  function <pair <int, int>(int, int, int, int, int)> get = [&](int index, int L, int R, int l, int r) {
    lazyUpdate(index, L, R); 
    pair <int, int> ret = make_pair(-1000000007, 1000000007); 
    if (l > R || L > r) {
      return ret; 
    }
    if (l <= L && R <= r) {
      return make_pair(it[index].maxValue, it[index].minValue); 
    }
    int mid = (L + R) / 2; 
    pair <int, int> getLeft = get(2 * index, L, mid, l, r); 
    pair <int, int> getRight = get(2 * index + 1, mid + 1, R, l, r); 
    return make_pair(max(getLeft.first, getRight.first), min(getLeft.second, getRight.second)); 
  };
  function <long long(int, int, int, int, int)> get_sum = [&](int index, int L, int R, int l, int r) {
    lazyUpdate(index, L, R); 
    if (L > r || l > R) {
      return 0LL; 
    }
    if (l <= L && R <= r) {
      return it[index].sum; 
    }
    int mid = (L + R) / 2; 
    long long getLeft = get_sum(2 * index, L, mid, l, r); 
    long long getRight = get_sum(2 * index + 1, mid + 1, R, l, r); 
    return getLeft + getRight; 
  };
  function <int(int, int, int, int)> find_next_left = [&](int index, int L, int R, int need) {
    lazyUpdate(index, L, R); 
    if (L == R) {
      return L; 
    }
    int mid = (L + R) / 2; 
    if (it[2 * index].minValue <= need && need <= it[2 * index].maxValue) {
      return find_next_left(2 * index, L, mid, need); 
    }
    else {
      return find_next_left(2 * index + 1, mid + 1, R, need); 
    }
  };
  function <int(int, int, int, int)> find_next_right = [&](int index, int L, int R, int need) {
    lazyUpdate(index, L, R);
    if (L == R) {
      return L; 
    }
    int mid = (L + R) / 2; 
    if (it[2 * index + 1].minValue <= need && need <= it[2 * index + 1].maxValue) {
      return find_next_right(2 * index + 1, mid + 1, R, need); 
    }
    else {
      return find_next_right(2 * index, L, mid, need); 
    }
  };
  function <void(int, int, int, int)> get_more = [&](int index, int L, int R, int position) { 
    lazyUpdate(index, L, R); 
    if (L > position || R < position) { 
      return; 
    } 
    if (L == R) { 
      it[index].maxValue = 0; 
      it[index].minValue = 0; 
      it[index].moreValue = 0; 
      it[index].sum = 0LL; 
      return; 
    } 
    int mid = (L + R) / 2; 
    get_more(2 * index, L, mid, position); 
    get_more(2 * index + 1, mid + 1, R, position); 
    it[index].maxValue = max(it[2 * index].maxValue, it[2 * index + 1].maxValue); 
    it[index].minValue = min(it[2 * index].minValue, it[2 * index + 1].minValue); 
    it[index].sum = it[2 * index].sum + it[2 * index + 1].sum; 
  };
  long long ans = 0LL; 
  for (int height = 1; height <= 100000; height++) {
    get_more(1, 1, 100000, height);
    for (auto id: save[height]) {
      int numb = a[id].second;
      ans += get_sum(1, 1, 100000, height - numb + 1, height);
      pair <int, int> pr = get(1, 1, 100000, height - numb + 1, height);
      int posLeft = find_next_left(1, 1, 100000, pr.first);
      int posRight = find_next_right(1, 1, 100000, pr.first);
      int numbSmaller = height - posRight;
      int numbLarger = numb - numbSmaller;
      update(1, 1, 100000, posLeft, posLeft + numbLarger - 1);
      if (numbSmaller > 0) {
        update(1, 1, 100000, posRight + 1, height); 
      }     
    }  
  }
  cout << ans; 
  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