oj.uz

Submission #489835

# Submission time Handle Problem Language Result Execution time Memory
489835 2021-11-24T21:15:17 Z czhang2718 trapezoid (balkan11_trapezoid) C++17
46 / 100
 342 ms 31740 KB 
#include "bits/stdc++.h"
using namespace std;

const int N=100001;
int n;
int ans[N], cnt[N];
int a[N], b[N];
map<int, int> trap, mx, mp;
vector<int> x;

struct segtree{
  int n;
  vector<int> sum;

  segtree(int n){
    this->n=n;
    sum.resize(4*n);
  }

  void add(int i, int v, int x, int lx, int rx){
    sum[x]+=v;
    if(rx-lx==1) return;
    int m=(lx+rx)/2;
    if(i<m) add(i, v, 2*x+1, lx, m);
    else add(i, v, 2*x+2, m, rx);
    sum[x]=sum[2*x+1]+sum[2*x+2];
  }

  void add(int i, int v){
    add(i, v, 0, 0, n);
  }

  int get_sum(int l, int r, int x, int lx, int rx){
    if(lx>=l && rx<=r) return sum[x];
    if(lx>=r || rx<=l) return 0;
    int m=(lx+rx)/2;
    return get_sum(l, r, 2*x+1, lx, m)+get_sum(l, r, 2*x+2, m, rx);
  }

  int get_sum(int l, int r){
    return get_sum(l, r, 0, 0, n);
  }

  int get_sum(){
    return get_sum(0, n);
  }
};

void solve1(){
  set<int> s={0};
  
  for(int xi:x){
    int i=trap[xi];
    if(!ans[i]){
      ans[i]=mx[*--s.lower_bound(a[i])]+1;
    }
    else{
      int prv=mx[*--s.lower_bound(b[i])];
      if(prv>ans[i]) continue;
      mx[b[i]]=ans[i];
      set<int>::iterator it;
      while((it=s.upper_bound(b[i]))!=s.end() && mx[*it]<ans[i]) s.erase(it); 
      s.insert(b[i]);
    }
  }

  cout << mx[*--s.end()] << " ";
}

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

void solve2(){
  vector<vector<int>> cc(n+1);
  for(int i=1; i<=n; i++){
    cc[ans[i]].push_back(i);
  }
  vector<segtree> st;
  segtree temp(1); st.push_back(temp);
  for(int i=1; i<=n; i++){
    sort(cc[i].begin(), cc[i].end(), cmp);
    for(int j=0; j<cc[i].size(); j++){
      mp[b[cc[i][j]]]=j;
    }
    segtree tree(cc[i].size()); 
    st.push_back(tree);
  }

  set<int> s={0};
  for(int xi:x){
    int i=trap[xi];
    if(!cnt[i]){
      int lst=*--s.lower_bound(a[i]);
      int k=ans[i]-1;
      cnt[i]=(k==0?1:st[k].get_sum(0, mp[lst]+1));
    }
    else{
      int prv=mx[*--s.lower_bound(b[i])];
      if(prv>ans[i]) continue;
      set<int>::iterator it;
      while((it=s.upper_bound(b[i]))!=s.end() && mx[*it]<ans[i]) s.erase(it); // don't need to clear segtree
      s.insert(b[i]);
      int k=ans[i];
      int j=mp[b[i]];
      st[k].add(j, cnt[i]);
    }
  }
  int k=mx[*--s.end()];
  cout << st[k].get_sum();
}

int main(){
  cin.tie(0)->sync_with_stdio(0);

  cin >> n;
  for(int i=1; i<=n ;i++){
    int c, d; cin >> a[i] >> b[i] >> c >> d;
    trap[c]=trap[d]=i;
    x.push_back(c); x.push_back(d);
  }

  sort(x.begin(), x.end());

  solve1();
  solve2();
}
// point add range sum

Compilation message

trapezoid.cpp: In function 'void solve2()':
trapezoid.cpp:83:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   83 |     for(int j=0; j<cc[i].size(); j++){
      |                  ~^~~~~~~~~~~~~

Subtask #1
46.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 336 KB Output is correct
2 Correct 0 ms 336 KB Output is correct
3 Partially correct 2 ms 464 KB Partially correct
4 Partially correct 2 ms 592 KB Partially correct
5 Partially correct 5 ms 976 KB Partially correct
6 Partially correct 8 ms 1332 KB Partially correct
7 Partially correct 6 ms 1488 KB Partially correct
8 Partially correct 9 ms 1872 KB Partially correct
9 Partially correct 22 ms 3456 KB Partially correct
10 Partially correct 33 ms 6160 KB Partially correct
11 Partially correct 70 ms 8204 KB Partially correct
12 Partially correct 115 ms 14740 KB Partially correct
13 Partially correct 158 ms 17736 KB Partially correct
14 Partially correct 202 ms 22564 KB Partially correct
15 Partially correct 197 ms 22840 KB Partially correct
16 Partially correct 196 ms 23800 KB Partially correct
17 Partially correct 231 ms 25612 KB Partially correct
18 Partially correct 214 ms 27092 KB Partially correct
19 Partially correct 324 ms 31520 KB Partially correct
20 Partially correct 342 ms 31740 KB Partially correct