oj.uz

Submission #223692

# Submission time Handle Problem Language Result Execution time Memory
223692 2020-04-16T05:04:44 Z FieryPhoenix Sails (IOI07_sails) C++11
0 / 100
 908 ms 10872 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) 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
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 85 ms 10744 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 85 ms 10872 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Runtime error 82 ms 10744 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Runtime error 160 ms 10872 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 908 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 907 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 907 ms 5700 KB Output isn't correct

Subtask #8
0 / 10.0

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

Subtask #9
0 / 10.0

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

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 907 ms 6264 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 6240 KB Output isn't correct
2 Halted 0 ms 0 KB -