oj.uz

답안 #489837

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
489837 2021-11-24T21:25:46 Z czhang2718 사다리꼴 (balkan11_trapezoid) C++17
100 / 100
 349 ms 29036 KB 
#include "bits/stdc++.h"
using namespace std;

const int N=100001;
const int MOD=30013;
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])%MOD;
  }

  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))%MOD;
  }

  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:84:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for(int j=0; j<cc[i].size(); j++){
      |                  ~^~~~~~~~~~~~~

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 204 KB Output is correct
2 Correct 0 ms 332 KB Output is correct
3 Correct 1 ms 460 KB Output is correct
4 Correct 2 ms 588 KB Output is correct
5 Correct 5 ms 844 KB Output is correct
6 Correct 7 ms 1288 KB Output is correct
7 Correct 6 ms 1476 KB Output is correct
8 Correct 13 ms 1740 KB Output is correct
9 Correct 22 ms 3180 KB Output is correct
10 Correct 34 ms 5720 KB Output is correct
11 Correct 66 ms 7516 KB Output is correct
12 Correct 114 ms 13384 KB Output is correct
13 Correct 159 ms 16244 KB Output is correct
14 Correct 204 ms 20664 KB Output is correct
15 Correct 186 ms 20680 KB Output is correct
16 Correct 194 ms 21564 KB Output is correct
17 Correct 230 ms 23304 KB Output is correct
18 Correct 204 ms 24704 KB Output is correct
19 Correct 324 ms 29008 KB Output is correct
20 Correct 349 ms 29036 KB Output is correct