oj.uz

Submission #683587

# Submission time Handle Problem Language Result Execution time Memory
683587 2023-01-18T19:11:07 Z Hacv16 Sails (IOI07_sails) C++17
100 / 100
 182 ms 7232 KB 
#include <bits/stdc++.h>
using namespace std;
 
#define int long long int

typedef long long ll;
const int MAX = 2e5 + 15;
const int INF = 1e18 + 10;
 
int n, fim, seg[4 * MAX], lzsum[4 * MAX];
vector<pair<int, int>> v;
 
void refresh(int p, int l, int r){
  if(lzsum[p] == 0) return;
  int add = lzsum[p];
  seg[p] += add;
  lzsum[p] = 0;
 
  if(l == r) return;
 
  int e = 2 * p, d = e + 1;
  lzsum[e] += add;
  lzsum[d] += 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){
    lzsum[p] += 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] = min(seg[e], seg[d]);
}
 
int getValue(int i, int p, int l, int r){
  if(l == r) return seg[p];
  refresh(p, l, r);
  int m = (l + r) >> 1, e = 2 * p, d = e + 1;
  refresh(e, l, m); refresh(d, m + 1, r);
  if(i <= m) return getValue(i, e, l, m);
  return getValue(i, d, m + 1, r);
}

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

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

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

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

    if(pos <= h){
      update(pos, h, 1, 1, 1, fim);
      k -= h - pos + 1;
    }
  }

  int t = eq(val, 1, 1, fim);
  update(t, t + k - 1, 1, 1, 1, fim);
}
 
int32_t main(){
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
 
  cin >> n;
 
  for(int i = 0; i < n; i++){
    int h, k; cin >> h >> k;
    v.push_back({h, k});
    fim = max(fim, h);
  } 

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

  int i = 0;

  for(auto p : v){ add(p.first, p.second); }
 
  int ans = 0;
 
  for(int i = 1; i <= fim; i++){
    int cur = getValue(i, 1, 1, fim);
    ans += (cur * (cur - 1)) >> 1;
  }
 
  cout << ans << '\n';
  return 0;
}

Compilation message

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

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 212 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 0 ms 340 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 340 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 328 KB Output is correct
2 Correct 1 ms 340 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 468 KB Output is correct
2 Correct 16 ms 4436 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 1640 KB Output is correct
2 Correct 42 ms 1332 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 2172 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 70 ms 3792 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 127 ms 6576 KB Output is correct
2 Correct 118 ms 6604 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 139 ms 6952 KB Output is correct
2 Correct 79 ms 6468 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 182 ms 7232 KB Output is correct
2 Correct 116 ms 4032 KB Output is correct