oj.uz

Submission #223693

# Submission time Handle Problem Language Result Execution time Memory
223693 2020-04-16T05:06:03 Z FieryPhoenix Sails (IOI07_sails) C++11
25 / 100
 908 ms 6212 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);
  ld starts=clock();
  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 (;;){
    ld stops=clock();
    if ((stops-starts)/(ld)(CLOCKS_PER_SEC)>=0.9)
      break;
    pair<int,int>p=*s.rbegin();
    int j=-p.second;
    s.erase(s.find(*s.rbegin()));
    if (j==1) break;
    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 32 ms 5376 KB Output is correct
2 Correct 29 ms 5376 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 5376 KB Output is correct
2 Correct 29 ms 5368 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 5368 KB Output is correct
2 Correct 28 ms 5376 KB Output is correct

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 5496 KB Output is correct
2 Incorrect 908 ms 5464 KB Output isn't correct

Subtask #5
0 / 10.0

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

Subtask #6
0 / 10.0

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

Subtask #7
0 / 10.0

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

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

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

Subtask #11
0 / 10.0

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