이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include <bits/stdc++.h>
#define sts(v) stable_sort(v.BE, v.E)
#define Rsts(v) stable_sort(v.rBE, v.rE)
#define rev(v) reverse(v.BE, v.E)
#define BE begin()
#define rBE rbegin()
#define E end()
#define rE rend()
#define pb push_back
#define ppb pop_back()
#define pf push_front
#define ppf pop_front()
#define F first
#define S second
using namespace std;
using ll = long long;
using T = pair<ll, ll>;
const int M = 998244353;
struct ABI{
vector<pair<int, int>> abi;
ABI(int n){
abi.resize(n + 1);
}
void updt(int ini, int val){
for(int i = ini; i < (int)abi.size(); i += i & -i)
if(abi[i].F < val)
abi[i] = {val, ini};
}
pair<int, int> query(int i){
pair<int, int> ans = {0, 0};
for(; i > 0; i -= i & -i)
if(ans.F < abi[i].F)
ans = abi[i];
return ans;
}
};
int bs(vector<int> &v, int val) {
int l = 1, r = v.size() - 1, ans = -1;
while(l < r) {
int m = (l + r) / 2;
if(v[m] <= val) l = m + 1, ans = m;
else r = m - 1;
}
return ans;
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// st para guardar la respuesta en la caja i
// dp[i] = query(1, n - 1)
int n, m; cin >> n >> m;
vector<pair<int, int>> v(n + 1, {INT_MIN, INT_MIN});
vector<int> F(m + 1, INT_MIN);
for(int i = 1; i <= n; i++){
int w, val; cin >> w >> val;
v[i] = {val, w};
}
for(int i = 1; i <= m; i++)
cin >> F[i];
sts(F);
sts(v);
int res = 0;
ABI abi(m);
for(int i = 1; i <= n; i++){
int k = lower_bound(F.BE, F.E, v[i].S) - F.BE;
if(k == m + 1)continue;
pair<int, int> ans = abi.query(m - 1);
if(!ans.F)ans = {1, k};
else{
ans.F++;
if(k > ans.S)ans.S = k;
else ans.S++;
}
abi.updt(ans.S, ans.F);
//val, pos
res = max(res, ans.F);
}
cout << res;
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |