oj.uz

답안 #986294

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
986294 2024-05-20T09:16:43 Z abczz Sails (IOI07_sails) C++14
10 / 100
 48 ms 4728 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;
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

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.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 348 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
10.0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 344 KB Output is correct
2 Correct 1 ms 348 KB Output is correct

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 1 ms 600 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 2 ms 856 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 4 ms 856 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 15 ms 1860 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 24 ms 2652 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 45 ms 3664 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 43 ms 4432 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# 결과 실행 시간 메모리 Grader output
1 Runtime error 48 ms 4728 KB Execution killed with signal 6
2 Halted 0 ms 0 KB -