oj.uz

Submission #74725

# Submission time Handle Problem Language Result Execution time Memory
74725 2018-09-07T03:08:56 Z goodbaton Sails (IOI07_sails) C++14
100 / 100
 42 ms 8448 KB 
#include <cstdio>
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>

using namespace std;
typedef long long ll;

#define SIZE 100010

int main(){
  int n,h,k,max_h=0;
  ll sum[SIZE] = {};
  priority_queue<pair<ll,ll> > pq;

  scanf("%d",&n);

  for(int i=0;i<n;i++){
    scanf("%d%d",&h,&k);
    max_h = max(max_h,h);
    
    sum[h]++;
    sum[h-k]--;
  }
  
  for(int i=max_h;i>0;i--){
    sum[i-1] += sum[i];
  }

  for(int i=1;i<=max_h;i++){
    ll v = 1;
    sum[i] *= -1;
    
    while(pq.size() && pq.top().first > sum[i]/v){
      pair<ll,ll> p = pq.top();
      pq.pop();
      sum[i] += p.first * p.second;
      v += p.second;
    }

    sum[i] *= -1;
    
    if(sum[i]%v==0){
      pq.push(make_pair(-(sum[i]/v),v));
    }else{
      pq.push(make_pair(-(sum[i]/v+1),sum[i]%v));
      pq.push(make_pair(-(sum[i]/v),v-sum[i]%v));
    }

  }

  ll ans = 0;

  while(pq.size()){
    pair<ll,ll> p = pq.top();
    pq.pop();

    p.first *= -1;
    ans += p.first*(p.first-1)/2 * p.second;
  }

  printf("%lld\n",ans);

  return 0;
}

Compilation message

sails.cpp: In function 'int main()':
sails.cpp:17:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&n);
   ~~~~~^~~~~~~~~
sails.cpp:20:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d%d",&h,&k);
     ~~~~~^~~~~~~~~~~~~~

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1144 KB Output is correct
2 Correct 2 ms 1152 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1328 KB Output is correct
2 Correct 3 ms 1380 KB Output is correct

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1384 KB Output is correct
2 Correct 3 ms 1388 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1424 KB Output is correct
2 Correct 27 ms 1844 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 1872 KB Output is correct
2 Correct 10 ms 1872 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 2768 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 3356 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 35 ms 3752 KB Output is correct
2 Correct 37 ms 5140 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 7708 KB Output is correct
2 Correct 38 ms 8380 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 8380 KB Output is correct
2 Correct 33 ms 8448 KB Output is correct