Submission #1311592

#	Time	Username	Problem	Language	Result	Execution time	Memory
1311592		vyaduct	Matryoshka (JOI16_matryoshka)	C++20	100 / 100	300 ms	14380 KiB

matryoshka

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> pll;

const int mxN = 200001;
pll dolls[mxN];
pair<pll, ll> qrys[mxN];
ll ans[mxN];

/*
  claim: 
    the minimum number of towers is the LDS
    of the selected items when R[] is sorted
*/

void solve(){
  int n,q; cin>>n>>q;
  for (int i=0;i<n;i++) { 
    cin>>dolls[i].first>>dolls[i].second;
    dolls[i].second *= -1;
  }
  for (int i=0;i<q;i++){
    cin>>qrys[i].first.first>>qrys[i].first.second;
    qrys[i].second = i;
  }

  sort(dolls, dolls + n, greater<>());
	sort(qrys, qrys + q, greater<>());

	vector<pll> dp;
  const ll INF = 1e9;
	for (int i=0, j=0;i<q;i++){
    while(j<n && dolls[j].first >= qrys[i].first.first){
      pll X = make_pair(-dolls[j].second, INF);
      int lds = upper_bound(dp.begin(), dp.end(),  X) - dp.begin();
      if (lds == dp.size()) dp.push_back(make_pair(-dolls[j].second, dolls[j].first));
      else dp[lds] = {-dolls[j].second, dolls[j].first};
      j++;
    }
    ans[qrys[i].second] = upper_bound(dp.begin(), dp.end(), make_pair(qrys[i].first.second, INF)) - dp.begin();
  }
  for (int i=0;i<q;i++){
    cout << ans[i] << "\n";
  }
}

int main(){
  solve();
}

• Subtask 1: 11 / 11
• Subtask 2: 15 / 15
• Subtask 3: 25 / 25
• Subtask 4: 49 / 49