Submission #987340

#	Time	Username	Problem	Language	Result	Execution time	Memory
987340		huutuan	Sails (IOI07_sails)	C++14	100 / 100	116 ms	13912 KiB

sails

#include<bits/stdc++.h>

using namespace std;

#define int long long

struct Node{
   int min_val, max_val;
   int lazy;
   Node (int _min_val=0, int _max_val=0){
      min_val=_min_val, max_val=_max_val, lazy=0;
   }
   Node operator+(const Node &b){
      return Node(min(min_val, b.min_val), max(max_val, b.max_val));
   }
};

struct SegmentTree{
   int n;
   vector<Node> t;
   void init(int _n){
      n=_n;
      t.assign(4*n+1, Node());
   }
   void apply(int k, int val){
      t[k].min_val+=val;
      t[k].max_val+=val;
      t[k].lazy+=val;
   }
   void push(int k){
      if (t[k].lazy){
         apply(k<<1, t[k].lazy);
         apply(k<<1|1, t[k].lazy);
         t[k].lazy=0;
      }
   }
   void update(int k, int l, int r, int L, int R, int val){
      if (r<L || R<l) return;
      if (L<=l && r<=R){
         apply(k, val);
         return;
      }
      push(k);
      int mid=(l+r)>>1;
      update(k<<1, l, mid, L, R, val);
      update(k<<1|1, mid+1, r, L, R, val);
      t[k]=t[k<<1]+t[k<<1|1];
   }
   int walkl(int k, int l, int r, int val){
      if (l==r) return l;
      push(k);
      int mid=(l+r)>>1;
      if (t[k<<1].min_val>val) return walkl(k<<1|1, mid+1, r, val);
      return walkl(k<<1, l, mid, val);
   }
   int walkr(int k, int l, int r, int val){
      if (l==r) return l;
      push(k);
      int mid=(l+r)>>1;
      if (t[k<<1|1].max_val<val) return walkr(k<<1, l, mid, val);
      return walkr(k<<1|1, mid+1, r, val);
   }
   int get(int k, int l, int r, int pos){
      if (l==r) return t[k].min_val;
      push(k);
      int mid=(l+r)>>1;
      if (pos<=mid) return get(k<<1, l, mid, pos);
      return get(k<<1|1, mid+1, r, pos);
   }
   int answer(int k, int l, int r){
      if (l==r) return t[k].min_val*(t[k].min_val-1)/2;
      push(k);
      int mid=(l+r)>>1;
      return answer(k<<1, l, mid)+answer(k<<1|1, mid+1, r);
   }
} st;

const int N=1e5+10;
int n;
int a[N], b[N];
pair<int, int> c[N];

int32_t main(){
   ios_base::sync_with_stdio(false);
   cin.tie(nullptr);
   cin >> n;
   for (int i=1; i<=n; ++i) cin >> a[i] >> b[i], c[i]={a[i], b[i]};
   sort(c+1, c+n+1);
   st.init(1e5);
   for (int i=1; i<=n; ++i){
      a[i]=c[i].first, b[i]=c[i].second;
      vector<pair<int, int>> v;
      int val=st.get(1, 1, st.n, a[i]-b[i]+1);
      int l=st.walkl(1, 1, st.n, val), r=st.walkr(1, 1, st.n, val);
      r=min(r, a[i]);
      st.update(1, 1, st.n, r+1, a[i], 1);
      int cnt=b[i]-(a[i]-(r+1)+1);
      st.update(1, 1, st.n, l, l+cnt-1, 1);
   }
   cout << st.answer(1, 1, st.n) << '\n';
   return 0;
}

• Subtask 1: 5 / 5
• Subtask 2: 10 / 10
• Subtask 3: 10 / 10
• Subtask 4: 5 / 5
• Subtask 5: 10 / 10
• Subtask 6: 10 / 10
• Subtask 7: 10 / 10
• Subtask 8: 10 / 10
• Subtask 9: 10 / 10
• Subtask 10: 10 / 10
• Subtask 11: 10 / 10