Submission #683232

#	Time	Username	Problem	Language	Result	Execution time	Memory
683232		Hacv16	Sails (IOI07_sails)	C++17	25 / 100	162 ms	8780 KiB

sails

#include <bits/stdc++.h>
using namespace std;
 
typedef long long ll;
const int MAX = 1e5 + 15;
const int INF = 0x3f3f3f3f;
 
struct Node{
  int f, mn, mx, lzsum;
 
  Node(int a = 0, int b = 0, int c = 0, int d = 0){
    f = a, mn = b, mx = c, lzsum = d;
  }
 
  Node operator + (Node other){
    if(f == other.f) return Node(f, min(mn, other.mn), max(mx, other.mx), 0);
    if(f < other.f) return Node(f, mn, mx, 0);
    return other;
  }
};
 
int n, fim;
vector<pair<int, int>> v;
Node seg[4 * MAX];
 
void build(int p, int l, int r){
  if(l == r){
    seg[p].f = 0;
    seg[p].mn = l;
    seg[p].mx = l;
    seg[p].lzsum = 0;
    return;
  }
 
  int m = (l + r) >> 1, e = 2 * p, d = e + 1;
  build(e, l, m); build(d, m + 1, r);
 
  seg[p] = seg[e] + seg[d];
}
 
void refresh(int p, int l, int r){
  if(seg[p].lzsum == 0) return;
  int add = seg[p].lzsum;
  seg[p].f += add;
  seg[p].lzsum = 0;
 
  if(l == r) return;
 
  int e = 2 * p, d = e + 1;
  seg[e].lzsum += add;
  seg[d].lzsum += add;
}
 
void update(int a, int b, int x, int p, int l, int r){
  refresh(p, l, r);
 
  if(a > r || b < l) return;
  if(a <= l && r <= b){
    seg[p].lzsum += x;
    refresh(p, l, r);
    return;
  }
 
  int m = (l + r) >> 1, e = 2 * p, d = e + 1;
  update(a, b, x, e, l, m);
  update(a, b, x, d, m + 1, r);
 
  seg[p] = seg[e] + seg[d];
}
 
Node query(int a, int b, int p, int l, int r){
  refresh(p, l, r);
 
  if(a > r || b < l) return Node(INF, INF, -INF, 0);
  if(a <= l && r <= b) return seg[p];
  int m = (l + r) >> 1, e = 2 * p, d = e + 1;
  return query(a, b, e, l, m) + query(a, b, d, m + 1, r); 
}

int bb(int x, int p, int l, int r){ //first lower
  if(l == r) return l;
  refresh(p, l, r);
  int m = (l + r) >> 1, e = 2 * p, d = e + 1;
  if(seg[e].f < x) return bb(x, e, l, m);
  return bb(x, d, m + 1, r);
}
 
int eq(int x, int p, int l, int r){ //first equal
  if(l == r) return l;
  refresh(p, l, r);
  int m = (l + r) >> 1, e = 2 * p, d = e + 1;
  if(seg[e].f <= x) return eq(x, e, l, m);
  return eq(x, d, m + 1, r);
}

void add(int h, int k){
  int val = query(h - k + 1, h - k + 1, 1, 1, fim).f;

  if(seg[1].f < val){
    int pos = bb(val, 1, 1, fim);

    if(pos <= h){
      update(pos, h, 1, 1, 1, fim);
      //cerr << "ADDED IN INTERVAL " << pos << ' ' << h << '\n';
      k -= (h - pos + 1);
    }
  }

  int t = eq(val, 1, 1, fim);
  update(t, t + k - 1, 1, 1, 1, fim);
  //cerr << "ADDED IN INTERVAL " << t << ' ' << t + k - 1 << '\n';
}
 
int main(void){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
 
  cin >> n;
 
  for(int i = 1; i <= n; i++){
    int h, k; cin >> h >> k;
    v.emplace_back(h, k);
    fim = max(fim, h);
  } 
 
  sort(v.begin(), v.end());
 
  build(1, 1, fim);
 
  int i = 1;

  for(auto p : v){ add(p.first, p.second); }
 
  ll ans = 0;
 
  for(int i = 1; i <= fim; i++){
    ll cur = query(i, i, 1, 1, fim).f;
    ans += (cur * (cur - 1)) / 2;
  }
 
  cout << ans << '\n';
 
  exit(0);
}

Compilation message (stderr)

sails.cpp: In function 'int main()':
sails.cpp:130:7: warning: unused variable 'i' [-Wunused-variable]
  130 |   int i = 1;
      |       ^

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