oj.uz

Submission #986320

# Submission time Handle Problem Language Result Execution time Memory
986320 2024-05-20T10:11:06 Z abczz Sails (IOI07_sails) C++14
40 / 100
 1000 ms 3060 KB 
#include <iostream>
#include <array>
#include <algorithm>
#include <queue>
#include <map>
#define ll long long

using namespace std;

ll n, p, l, r, y, f;
vector <ll> V;
map <ll, array<ll, 2> > mp;
array<ll, 2> A[100000];

void merge(ll x) {
  auto it = mp.find(x);
  if (it != mp.begin()) {
    auto pv = prev(it);
    auto z = pv->second[0];
    if (pv->second[1] == it->second[1]) {
      mp.erase(pv);
      mp[x] = {z, it->second[1]};
    }
  }
}
int main() {
  cin >> n;
  for (int i=0; i<n; ++i) {
    cin >> A[i][0] >> A[i][1];
  }
  sort(A, A+n);
  for (int i=0; i<n; ++i) {
    --A[i][0];
    if (p <= A[i][0]) {
      mp[A[i][0]] = {p, 0};
      merge(A[i][0]);
    }
    p = max(p, A[i][0]+1);
    auto it = prev(mp.end());
    V.clear();
    while (A[i][1]) {
      r = it->first, l = it->second[0], y = it->second[1];
      if (r-l+1 <= A[i][1]) {
        A[i][1] -= r-l+1;
        mp[r] = {l, it->second[1]+1};
        V.push_back(r);
      }
      else {
        mp.erase(it);
        mp[l+A[i][1]-1] = {l, y+1};
        V.push_back(l+A[i][1]-1);
        mp[r] = {l+A[i][1], y};
        break;
      }
      it = prev(it);
    }
    for (auto u : V) {
      merge(u);
    }
  }
  for (auto [x, z] : mp) {
    r = x, l = z[0], y = z[1];
    f += (r-l+1) * y * (y-1) / 2;
  }
  cout << f << '\n';
}

Compilation message

sails.cpp: In function 'int main()':
sails.cpp:61:13: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   61 |   for (auto [x, z] : mp) {
      |             ^

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 348 KB Output is correct
2 Correct 2 ms 344 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 52 ms 348 KB Output is correct
2 Correct 2 ms 348 KB Output is correct

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 869 ms 664 KB Output is correct
2 Execution timed out 1088 ms 1524 KB Time limit exceeded
3 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1045 ms 1620 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1020 ms 2104 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1059 ms 2408 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1057 ms 3060 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1010 ms 2856 KB Time limit exceeded
2 Halted 0 ms 0 KB -