oj.uz

Submission #683189

# Submission time Handle Problem Language Result Execution time Memory
683189 2023-01-17T22:38:03 Z Hacv16 Sails (IOI07_sails) C++17
5 / 100
 165 ms 8768 KB 
#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(), greater<pair<int, int>>());

  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
5.0 / 5.0

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

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 6484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 6484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 6484 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 8 ms 6620 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 6740 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 57 ms 7256 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 74 ms 7640 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 130 ms 8624 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 154 ms 8652 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 165 ms 8768 KB Output isn't correct
2 Halted 0 ms 0 KB -