Submission #919519

#	Time	Username	Problem	Language	Result	Execution time	Memory
919519		iskhakkutbilim	Exhibition (JOI19_ho_t2)	C++17	0 / 100	1 ms	600 KiB

joi2019_ho_t2

#include <bits/stdc++.h>
using namespace std;

#define ff first
#define ss second
#define all(a) a.begin(), a.end()
const int mod = 1e9 + 7;
const int N = 1e5;
#define int long long




struct node{
    int ans, mx;
};
node UND =  {-mod, -mod};
struct Segtree{
  int n;
  vector<node> t;
  Segtree(int sz){
    n = sz;
    t.resize(n * 4, UND);
  };
  node merge(node A, node B){
    if(A.ans > B.ans) return A;
    if(B.ans > A.ans) return B;
    return (A.mx > B.mx ? B : A);
  }
  
  void update(int pos, pair<int, int> x, int v, int vl, int vr){
    if(vl == vr){
		if(t[v].ans > x.ff) return;
		if(t[v].ans == x.ff && t[v].mx < x.ss) return;
		t[v] = {x.ff, x.ss};
		return;
	}
	int mid = (vl + vr)>>1;
	if(mid >= pos) update(pos, x, v<<1, vl, mid);
	else update(pos, x, v<<1|1, mid+1, vr);
    t[v] = merge(t[v<<1], t[v<<1|1]);
  }
  node get(int l, int r, int v, int vl, int vr){
    if(l > vr or vl > r) return UND;
    if(l <= vl and r >= vr) return t[v];
    int mid = (vl + vr)>>1;
    return merge(get(l, r, v<<1, vl, mid), get(l, r, v<<1|1, mid+1, vr));
  }  
};







signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int n, m; cin >> n >> m;
	vector< array<int, 2> > a(n);
	for(int i = 0;i < n; i++){
		cin >> a[i][0] >> a[i][1];
	}
	sort(all(a), [&](auto A, auto B){
		return A[1] < B[1];
	});
	vector<int> frame(m);
	for(auto &e : frame) cin >> e; 
	sort(all(frame));
	vector<int> x = frame;
	for(auto [A, B] : a){
		x.push_back(A);
	}
	sort(all(x));
	x.erase(unique(all(x)), x.end());	
	auto get=[&](int el){
		return upper_bound(all(x), el) - x.begin();
	};
	
	for(auto &e : frame) e = get(e);
	for(auto &[A, B] : a) A = get(A);
	int SIZ = x.size();
	Segtree seg(SIZ+1);
	seg.update(0, {0, 0}, 1, 0, SIZ);
	
	
	x = frame;
	frame.clear();
	frame.push_back(0);
	for(int e : x) frame.push_back(e);	
	for(auto [A, NA] : a){
		node got = seg.get(0, A, 1, 0, SIZ);
		int to = max(got.mx + 1, (int)(lower_bound(all(frame), A) - frame.begin()));
		if(to < frame.size())
		seg.update(A, {got.ans+1, to}, 1, 0, SIZ);
	}
	
	node got = seg.get(0, SIZ, 1, 0, SIZ);
	cout  << got.ans;
		
	return 0;
}

Compilation message (stderr)

joi2019_ho_t2.cpp: In function 'int main()':
joi2019_ho_t2.cpp:95:9: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |   if(to < frame.size())
      |      ~~~^~~~~~~~~~~~~~

• Subtask 1: 0 / 10
• Subtask 2: 0 / 40
• Subtask 3: 0 / 50