Submission #1018012

#	Time	Username	Problem	Language	Result	Execution time	Memory
1018012		NintsiChkhaidze	Sails (IOI07_sails)	C++17	30 / 100	1046 ms	11968 KiB

sails

#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 / 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