Submission #683190

#	Time	Username	Problem	Language	Result	Execution time	Memory
683190		Hacv16	Sails (IOI07_sails)	C++17	0 / 100	139 ms	7756 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 add(int h, int k){ //retorna quantos faltam p fechar
  Node aux = query(1, h, 1, 1, fim);
  int top = aux.mx, bot = aux.mn;
  if(top - bot + 1 > k) bot = top - k + 1;

  //cerr << "TRYING TO ADD.. " << k << '\n';
  //cerr << "ADDED IN INTERVAL " << ' ' << bot << ' ' << top << " --> " << top - bot + 1 << '\n';

  update(bot, top, 1, 1, 1, fim);
  
  return k - (top - bot + 1);
}

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);

  for(auto p : v){
    int h = p.first, k = p.second;
    int rest = add(h, k);
    if(rest) add(h, rest);
  }

  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);
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 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