oj.uz

Submission #1018012

# Submission time Handle Problem Language Result Execution time Memory
1018012 2024-07-09T12:47:49 Z NintsiChkhaidze Sails (IOI07_sails) C++17
30 / 100
 1000 ms 11968 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define s second
#define f first
#define pii pair <int,int>
#define left h*2,l,(l + r)/2
#define right h*2+1,(l + r)/2 + 1,r
#define int ll
using namespace std;

const int N = 1e5 + 3,inf = 1e9;
int H[N],A[N],cnt[N];
pii t[4*N];
int arr[N];

bool cmp(int i,int j){
  return (H[i] < H[j]);
}

void build(int h,int l,int r){
  if (l == r){
    t[h] = {0,-l};
    return;
  }
  build(left);
  build(right);
  t[h] = min(t[h*2],t[h*2+1]);
}

pii get(int h,int l,int r,int L,int R){
  if (r < L || R< l) return {inf,0};
  if (L <= l && r <= R) return t[h];
  return min(get(left,L,R),get(right,L,R));
}

void upd(int h,int l,int r,int idx,int val){
  if (l == r) {
    t[h].f = val;
    return;
  }

  if (idx > (l + r)/2) upd(right,idx,val);
  else upd(left,idx,val);
  t[h] = min(t[h*2],t[h*2+1]);
}

signed main (){
  ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);

  int n;
  cin>>n;

  for (int i = 1; i <= n; i++){
    cin >> H[i] >> A[i];
    arr[i] = i;
  }

  sort(arr+1,arr+n+1,cmp);
  int m = 100000;
  ll ans=0;
  build(1,1,m);

  for (int ii= 1; ii <= n; ii++){
    int i = arr[ii];
    vector <pii> vec;
    for (int j = 1; j <= A[i]; j++){
      pii res = get(1,1,m,1,H[i]);
      vec.pb({res.f,-res.s});
      upd(1,1,m,-res.s,inf);
    }

    for (auto [x,y]: vec)
      upd(1,1,m,y,x + 1),ans += cnt[y],cnt[y]++;
  }

  cout<<ans;
}

Subtask #1
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6488 KB Output is correct
2 Correct 2 ms 6488 KB Output is correct

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 6488 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct

Subtask #3
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 6492 KB Output is correct
2 Correct 2 ms 6492 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 6492 KB Output is correct
2 Correct 38 ms 6492 KB Output is correct

Subtask #5
0 / 10.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1046 ms 6776 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 1038 ms 7260 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 1041 ms 7464 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 1032 ms 8032 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 1040 ms 11968 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 1035 ms 9040 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 1028 ms 9536 KB Time limit exceeded
2 Halted 0 ms 0 KB -