oj.uz

Submission #223691

# Submission time Handle Problem Language Result Execution time Memory
223691 2020-04-16T05:03:41 Z FieryPhoenix Sails (IOI07_sails) C++11
25 / 100
 141 ms 7440 KB 
#include <bits/stdc++.h>
using namespace std;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
typedef long long ll;
typedef long double ld;
#define INF 2001001001
#define MOD 1000000007

int N,H[100001],K[100001];
int cnt[100001];

int main()
{
  //ios_base::sync_with_stdio(0);cin.tie(0);
  //freopen (".in","r",stdin);
  //freopen (".out","w",stdout);
  cin>>N;
  for (int i=0;i<N;i++){
    cin>>H[i]>>K[i];
    cnt[H[i]-K[i]+1]++;
    cnt[H[i]+1]--;
  }
  for (int i=1;i<=100000;i++)
    cnt[i]+=cnt[i-1];
  set<pair<int,int>>s; //val, -ind
  for (int i=1;i<=100000;i++)
    s.insert({cnt[i],-i});
  for (int i=0;i<100000;i++){
    pair<int,int>p=*s.rbegin();
    int j=-p.second;
    s.erase(s.find(*s.rbegin()));
    if (j==1) continue;
    if (cnt[j]>cnt[j-1]){
      cnt[j]--;
      s.erase(s.find({cnt[j-1],-(j-1)}));
      cnt[j-1]++;
      s.insert({cnt[j],-j});
      s.insert({cnt[j-1],-(j-1)});
    }
  }
  ll ans=0;
  for (int i=1;i<=N;i++){
    ll x=cnt[i];
    ans+=(x*(x-1))/2;
  }
  cout<<ans<<endl;
  return 0;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 37 ms 5376 KB Output is correct
2 Correct 40 ms 5372 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 5376 KB Output is correct
2 Correct 37 ms 5376 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 5368 KB Output is correct
2 Correct 37 ms 5368 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 5376 KB Output is correct
2 Incorrect 71 ms 5376 KB Output isn't correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 66 ms 5496 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 67 ms 5504 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 88 ms 6044 KB Output isn't correct

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 102 ms 6380 KB Output isn't correct

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 125 ms 6868 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 135 ms 7204 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 141 ms 7440 KB Output isn't correct
2 Halted 0 ms 0 KB -