Submission #223692

#	Time	Username	Problem	Language	Result	Execution time	Memory
223692		FieryPhoenix	Sails (IOI07_sails)	C++11	0 / 100	908 ms	10872 KiB

sails

#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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 5
• Subtask 5: 0 / 10
• Subtask 6: 0 / 10
• Subtask 7: 0 / 10
• Subtask 8: 0 / 10
• Subtask 9: 0 / 10
• Subtask 10: 0 / 10
• Subtask 11: 0 / 10