oj.uz

Submission #528769

# Submission time Handle Problem Language Result Execution time Memory
528769 2022-02-21T11:19:56 Z cig32 Sails (IOI07_sails) C++17
30 / 100
 1000 ms 8140 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4296 KB Output is correct
2 Correct 22 ms 4276 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 24 ms 4300 KB Output is correct
2 Correct 27 ms 4300 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 20 ms 4380 KB Output is correct
2 Correct 21 ms 4296 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 23 ms 4432 KB Output is correct
2 Correct 74 ms 4424 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1076 ms 4496 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #6
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1047 ms 4764 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #7
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1081 ms 5256 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #8
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1072 ms 5796 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #9
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1068 ms 8140 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #10
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1044 ms 6900 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #11
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 7304 KB Time limit exceeded
2 Halted 0 ms 0 KB -