Submission #1191515

#	Time	Username	Problem	Language	Result	Execution time	Memory
1191515		julia_08	Sails (IOI07_sails)	C++20	100 / 100	143 ms	5736 KiB

sails

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

using ll = long long;

const int MAXN = 1e5 + 10;

struct node{
  ll max, lz;
};

int k[MAXN];

node seg[4 * MAXN];

void refresh(int x, int lx, int rx){

  if(lx != rx){
    int lc = 2 * x, rc = 2 * x + 1;
    seg[lc].lz += seg[x].lz;
    seg[rc].lz += seg[x].lz;
  }

  seg[x].max += seg[x].lz;
  seg[x].lz = 0;

}

void update(int x, int lx, int rx, int l, int r){
  refresh(x, lx, rx);

  if(rx < l || lx > r) return;

  if(l <= lx && rx <= r){
    seg[x].lz ++;
    refresh(x, lx, rx);
    return;
  }

  int m = (lx + rx) / 2, lc = 2 * x, rc = 2 * x + 1;

  update(lc, lx, m, l, r);
  update(rc, m + 1, rx, l, r);

  seg[x].max = max(seg[lc].max, seg[rc].max);
}

int bs(int x, int lx, int rx, int l, int r, int val){
  refresh(x, lx, rx);

  if(rx < l || lx > r || seg[x].max <= val) return -1;

  if(lx == rx) return lx;

  int m = (lx + rx) / 2, lc = 2 * x, rc = 2 * x + 1;

  int bs_r = bs(rc, m + 1, rx, l, r, val);

  if(bs_r != -1) return bs_r;
  return bs(lc, lx, m, l, r, val);
}

ll query(int x, int lx, int rx, int i){
  refresh(x, lx, rx);

  if(lx == rx) return seg[x].max;

  int m = (lx + rx) / 2, lc = 2 * x, rc = 2 * x + 1;

  if(i <= m) return query(lc, lx, m, i);
  return query(rc, m + 1, rx, i);
}

int main(){
  cin.tie(0)->sync_with_stdio(0);

  int n; cin >> n;

  vector<pair<int, int>> masts;

  int H = 0;

  for(int i=1; i<=n; i++){

    int h; cin >> h >> k[i];

    masts.push_back({h, i});
    H = max(H, h);

  }

  sort(masts.begin(), masts.end());

  for(auto [h, i] : masts){

    int j = h - k[i] + 1;

    int v_j = query(1, 1, H, j);

    int l_1 = bs(1, 1, H, 1, h, v_j) + 1;
    l_1 = max(l_1, 1);

    int l_2 = bs(1, 1, H, 1, h, v_j - 1) + 1;

    if(l_2 <= h) update(1, 1, H, l_2, h);
    update(1, 1, H, l_1, l_1 + (k[i] - (h - l_2 + 1)) - 1);

  }

  ll ans = 0;

  for(int i=1; i<=H; i++){
    ll q = query(1, 1, H, i);
    ans += (q * (q - 1)) / 2;
  }

  cout << ans << "\n";

  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