Submission #1128588

#	Time	Username	Problem	Language	Result	Execution time	Memory
1128588		AverageAmogusEnjoyer	Sails (IOI07_sails)	C++17	10 / 100	1096 ms	2712 KiB

sails

#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
template<class T> bool cmin(T &i, T j) { return i > j ? i=j,true:false; }
template<class T> bool cmax(T &i, T j) { return i < j ? i=j,true:false; }

mt19937 mrand(chrono::steady_clock::now().time_since_epoch().count());
uniform_int_distribution<int> ui(0, 1 << 30);

int rng() { 
  return ui(mrand);
}

const int N=100100;
int n;
int h[N],k[N];
int placed[N];
int order[N];

int st[4*N];
void upd(int p,int x,int u=1,int tl=0,int tr=N-1) {
  if (tl == tr) {
    st[u]=(x > 0 ? tl : N);
    return;
  }
  int mid=(tl+tr)/2;
  if (p <= mid)
    upd(p,x,2*u,tl,mid);
  else  
    upd(p,x,2*u+1,mid+1,tr);
  st[u]=min(st[2*u],st[2*u+1]);
}
int query(int l,int r,int u=1,int tl=0,int tr=N-1) {
  if (l > r) return N;
  if (l == tl && r == tr)
    return st[u];
  int mid=(tl+tr)/2;
  return min(query(l,min(mid,r),2*u,tl,mid),query(max(mid+1,l),r,2*u+1,mid+1,tr));
}
void build(int u=1,int tl=0,int tr=N-1) {
  st[u]=N;
  if (tl==tr) return;
  int mid=(tl+tr)/2;
  build(2*u,tl,mid);
  build(2*u+1,mid+1,tr);
}

int main() {
  ios_base::sync_with_stdio(false); 
  cin.tie(nullptr);
    
  cin >> n;
  for (int i=0;i<n;i++)
    cin >> h[i] >> k[i];
  iota(order,order+n,0);
  sort(order,order+n,[&](int i,int j) {
    return h[i] < h[j];
  });  
  int lh = 0;
  build();
  for (int t=0;t<n;t++) {
    int i = order[t];
    int diff = h[i] - lh;
    lh = h[i];
    placed[0] += diff;
    upd(0,placed[0]);
    vector<pair<int,int>> work;
    int l=-1;
    while(k[i]>0) {
      int j=query(l+1,N-1);
      assert(j<N);
      int now = min(k[i],placed[j]);
      placed[j]-=now;
      placed[j+1]+=now;
      work.emplace_back(j+1,placed[j+1]);
      work.emplace_back(j,placed[j]);      
      k[i] -= now;
      l = j; 
    }
    for (auto &[p,np]: work)
      upd(p,np);
    /*int j = 0;
    new_placed[0] = placed[0];
    for (;k[i]>0;j++) {
      int now = min(k[i],placed[j]);
      new_placed[j + 1] = placed[j + 1] + now;
      k[i] -= now;
      new_placed[j] -= now;
    }
    for (int z=0;z<=j;z++) 
      placed[z] = new_placed[z];
    */
  }

  ll ans = 0;
  for (int i=0;i<N;i++) {
    ans += 1LL * i * (i - 1) / 2 * placed[i];
  }
  cout << ans << endl;
} 

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 10 / 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