제출 #489837

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
489837		czhang2718	사다리꼴 (balkan11_trapezoid)	C++17	100 / 100	349 ms	29036 KiB

trapezoid

#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

컴파일 시 표준 에러 (stderr) 메시지

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