Submission #986294

#	Time	Username	Problem	Language	Result	Execution time	Memory
986294		abczz	Sails (IOI07_sails)	C++14	10 / 100	48 ms	4728 KiB

sails

#include <iostream>
#include <array>
#include <algorithm>
#include <queue>
#include <map>
#define ll long long

using namespace std;

ll n, p, l, r, y, f;
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());
    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};
        merge(r);
      }
      else {
        mp.erase(it);
        mp[l+A[i][1]-1] = {l, y+1};
        merge(l+A[i][1]-1);
        mp[r] = {l+A[i][1], y};
        break;
      }
      it = prev(it);
    }
    for (auto [x, z] : mp) {
      r = x, l = z[0], y = z[1];
    }
  }
  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 (stderr)

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

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