Submission #528769

#	Time	Username	Problem	Language	Result	Execution time	Memory
528769		cig32	Sails (IOI07_sails)	C++17	30 / 100	1081 ms	8140 KiB

sails

#include "bits/stdc++.h"
using namespace std;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 1e5 + 10;
const int MOD = 1e9 + 7;
#define int long long
 
int rnd(int x, int y) {
  int u = uniform_int_distribution<int>(x, y)(rng); return u;
}
struct mast {
  int height;
  int cnt;
};
bool cmp(mast a, mast b) {
  if(a.height == b.height) return a.cnt < b.cnt;
  return a.height < b.height;
}
pair<long long, int> a[4*MAXN] = {};
//To be remained unchanged by default
void u(int l, int r, int tar, int idx, long long val) {
  if(l == r) {
    a[idx].first += val;
    a[idx].second = tar;
    return;
  }
  int mid = (l+r) >> 1;
  if(tar <= mid) u(l, mid, tar, 2*idx+1, val);
  else u(mid+1, r, tar, 2*idx+2, val);
  a[idx] = min(a[2*idx+1], a[2*idx+2]);
}
pair<long long, int> qu(int l, int r, int constl, int constr, int idx) {
  if(l <= constl && constr <= r) return a[idx];
  int mid = (constl+constr) >> 1;
  if(mid < l || r < constl) return qu(l, r, mid+1, constr, 2*idx+2);
  if(constr < l || r < mid+1) return qu(l, r, constl, mid, 2*idx+1);
  return min(qu(l, r, constl, mid, 2*idx+1), qu(l, r, mid+1, constr, 2*idx+2));
}
//Convenience functions
void update(int i, int v) {
  u(0, MAXN-1, i, 0, v);
}
pair<long long, int> query(int l, int r) {
  return qu(l, r, 0, MAXN-1, 0);
}
void solve(int tc) {
  int n;
  cin >> n;
  mast m[n+1];
  for(int i=1; i<=n; i++) cin >> m[i].height >> m[i].cnt;
  sort(m+1, m+n+1, cmp);
  for(int i=1; i<=100000; i++) update(i, 0);
  for(int i=1; i<=n; i++) {
    vector<int> v;
    for(int j=1; j<=m[i].cnt; j++) {
      int oh = query(1, m[i].height).second;
      update(oh, MOD);
      v.push_back(oh);
    }
    for(int X: v) {
      update(X, 1 - MOD);
    }
  }
  int ans = 0;
  for(int i=1; i<=100000; i++) {
    int res = query(i, i).first;
    ans += res * (res-1) / 2;
  }
  cout << ans << "\n";
}
int32_t main(){
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1;// cin >> t;
  for(int i=1; i<=t; i++) solve(i);
} 

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