oj.uz

Submission #987340

# Submission time Handle Problem Language Result Execution time Memory
987340 2024-05-22T15:21:55 Z huutuan Sails (IOI07_sails) C++14
100 / 100
 116 ms 13912 KB 
#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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 11868 KB Output is correct
2 Correct 4 ms 11868 KB Output is correct

Subtask #2
10.0 / 10.0

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

Subtask #3
10.0 / 10.0

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

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12020 KB Output is correct
2 Correct 4 ms 11868 KB Output is correct

Subtask #5
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 11864 KB Output is correct
2 Correct 7 ms 11868 KB Output is correct

Subtask #6
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 12124 KB Output is correct
2 Correct 29 ms 12368 KB Output is correct

Subtask #7
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 12632 KB Output is correct

Subtask #8
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 12892 KB Output is correct

Subtask #9
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 86 ms 13404 KB Output is correct
2 Correct 73 ms 13404 KB Output is correct

Subtask #10
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 93 ms 13652 KB Output is correct
2 Correct 54 ms 13412 KB Output is correct

Subtask #11
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 116 ms 13912 KB Output is correct
2 Correct 74 ms 13912 KB Output is correct