| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 100560 |
2019-03-12T09:18:06 Z |
TAISA_ |
None (JOI16_matryoshka) |
C++14 |
|
771 ms |
19464 KB |
#include <bits/stdc++.h>
#define mp make_pair
#define all(vec) vec.begin(),vec.end()
using namespace std;
using ll=long long;
using P=pair<ll,ll>;
const ll INF=1LL<<30;
const ll LINF=1LL<<60;
const double eps=1e-9;
const ll MOD=1000000007LL;
template<typename T>void chmin(T &a,T b){a=min(a,b);};
template<typename T>void chmax(T &a,T b){a=max(a,b);};
template<typename T>vector<T> make_v(size_t a){return vector<T>(a);}
template<typename T,typename... Ts>auto make_v(size_t a,Ts... ts){return vector<decltype(make_v<T>(ts...))>(a,make_v<T>(ts...));}
template<typename T,typename V>typename enable_if<is_class<T>::value==0>::type fill_v(T& t,const V& v){t=v;}
template<typename T,typename V>typename enable_if<is_class<T>::value!=0>::type fill_v(T& t,const V& v){for(auto &e:t)fill_v(e,v);};
int dx[4]={0,1,0,-1};
int dy[4]={1,0,-1,0};
int main(){
int n,q;cin>>n>>q;
vector<P> v(n);
for(int i=0;i<n;i++){
cin>>v[i].first>>v[i].second;
v[i].second*=-1LL;
}
sort(all(v));
reverse(all(v));
for(int i=0;i<n;i++)v[i].second*=-1LL;
vector<pair<P,int>> qs(q);
vector<int> ans(q);
for(int i=0;i<q;i++){
cin>>qs[i].first.first>>qs[i].first.second;
qs[i].second=i;
}
sort(all(qs));
reverse(all(qs));
int id=0;
vector<ll> dp(n+10,LINF);
for(int i=0;i<q;i++){
ll a=qs[i].first.first,b=qs[i].first.second,idx=qs[i].second;
while(id<n&&a<=v[id].first){
*(upper_bound(all(dp),v[id].second))=v[id].second;
id++;
}
ans[idx]=upper_bound(all(dp),b)-dp.begin();
}
for(int i=0;i<q;i++)cout<<ans[i]<<endl;
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
256 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
3 ms |
384 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| 8 |
Correct |
2 ms |
256 KB |
Output is correct |
| 9 |
Correct |
2 ms |
384 KB |
Output is correct |
| 10 |
Correct |
2 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
256 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
3 ms |
384 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| 8 |
Correct |
2 ms |
256 KB |
Output is correct |
| 9 |
Correct |
2 ms |
384 KB |
Output is correct |
| 10 |
Correct |
2 ms |
384 KB |
Output is correct |
| 11 |
Correct |
2 ms |
384 KB |
Output is correct |
| 12 |
Correct |
2 ms |
256 KB |
Output is correct |
| 13 |
Correct |
2 ms |
256 KB |
Output is correct |
| 14 |
Correct |
2 ms |
256 KB |
Output is correct |
| 15 |
Correct |
3 ms |
384 KB |
Output is correct |
| 16 |
Correct |
2 ms |
256 KB |
Output is correct |
| 17 |
Correct |
2 ms |
256 KB |
Output is correct |
| 18 |
Correct |
2 ms |
384 KB |
Output is correct |
| 19 |
Correct |
2 ms |
384 KB |
Output is correct |
| 20 |
Correct |
2 ms |
256 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
256 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
3 ms |
384 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| 8 |
Correct |
2 ms |
256 KB |
Output is correct |
| 9 |
Correct |
2 ms |
384 KB |
Output is correct |
| 10 |
Correct |
2 ms |
384 KB |
Output is correct |
| 11 |
Correct |
2 ms |
384 KB |
Output is correct |
| 12 |
Correct |
2 ms |
256 KB |
Output is correct |
| 13 |
Correct |
2 ms |
256 KB |
Output is correct |
| 14 |
Correct |
2 ms |
256 KB |
Output is correct |
| 15 |
Correct |
3 ms |
384 KB |
Output is correct |
| 16 |
Correct |
2 ms |
256 KB |
Output is correct |
| 17 |
Correct |
2 ms |
256 KB |
Output is correct |
| 18 |
Correct |
2 ms |
384 KB |
Output is correct |
| 19 |
Correct |
2 ms |
384 KB |
Output is correct |
| 20 |
Correct |
2 ms |
256 KB |
Output is correct |
| 21 |
Correct |
2 ms |
384 KB |
Output is correct |
| 22 |
Correct |
5 ms |
384 KB |
Output is correct |
| 23 |
Correct |
8 ms |
384 KB |
Output is correct |
| 24 |
Correct |
9 ms |
384 KB |
Output is correct |
| 25 |
Correct |
9 ms |
384 KB |
Output is correct |
| 26 |
Correct |
8 ms |
512 KB |
Output is correct |
| 27 |
Correct |
11 ms |
384 KB |
Output is correct |
| 28 |
Correct |
10 ms |
384 KB |
Output is correct |
| 29 |
Correct |
11 ms |
384 KB |
Output is correct |
| 30 |
Correct |
7 ms |
384 KB |
Output is correct |
| 31 |
Correct |
13 ms |
384 KB |
Output is correct |
| 32 |
Correct |
10 ms |
384 KB |
Output is correct |
| 33 |
Correct |
10 ms |
384 KB |
Output is correct |
| 34 |
Correct |
9 ms |
384 KB |
Output is correct |
| 35 |
Correct |
8 ms |
384 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
2 ms |
384 KB |
Output is correct |
| 2 |
Correct |
2 ms |
256 KB |
Output is correct |
| 3 |
Correct |
2 ms |
384 KB |
Output is correct |
| 4 |
Correct |
2 ms |
384 KB |
Output is correct |
| 5 |
Correct |
2 ms |
384 KB |
Output is correct |
| 6 |
Correct |
3 ms |
384 KB |
Output is correct |
| 7 |
Correct |
2 ms |
384 KB |
Output is correct |
| 8 |
Correct |
2 ms |
256 KB |
Output is correct |
| 9 |
Correct |
2 ms |
384 KB |
Output is correct |
| 10 |
Correct |
2 ms |
384 KB |
Output is correct |
| 11 |
Correct |
2 ms |
384 KB |
Output is correct |
| 12 |
Correct |
2 ms |
256 KB |
Output is correct |
| 13 |
Correct |
2 ms |
256 KB |
Output is correct |
| 14 |
Correct |
2 ms |
256 KB |
Output is correct |
| 15 |
Correct |
3 ms |
384 KB |
Output is correct |
| 16 |
Correct |
2 ms |
256 KB |
Output is correct |
| 17 |
Correct |
2 ms |
256 KB |
Output is correct |
| 18 |
Correct |
2 ms |
384 KB |
Output is correct |
| 19 |
Correct |
2 ms |
384 KB |
Output is correct |
| 20 |
Correct |
2 ms |
256 KB |
Output is correct |
| 21 |
Correct |
2 ms |
384 KB |
Output is correct |
| 22 |
Correct |
5 ms |
384 KB |
Output is correct |
| 23 |
Correct |
8 ms |
384 KB |
Output is correct |
| 24 |
Correct |
9 ms |
384 KB |
Output is correct |
| 25 |
Correct |
9 ms |
384 KB |
Output is correct |
| 26 |
Correct |
8 ms |
512 KB |
Output is correct |
| 27 |
Correct |
11 ms |
384 KB |
Output is correct |
| 28 |
Correct |
10 ms |
384 KB |
Output is correct |
| 29 |
Correct |
11 ms |
384 KB |
Output is correct |
| 30 |
Correct |
7 ms |
384 KB |
Output is correct |
| 31 |
Correct |
13 ms |
384 KB |
Output is correct |
| 32 |
Correct |
10 ms |
384 KB |
Output is correct |
| 33 |
Correct |
10 ms |
384 KB |
Output is correct |
| 34 |
Correct |
9 ms |
384 KB |
Output is correct |
| 35 |
Correct |
8 ms |
384 KB |
Output is correct |
| 36 |
Correct |
579 ms |
16432 KB |
Output is correct |
| 37 |
Correct |
661 ms |
15736 KB |
Output is correct |
| 38 |
Correct |
196 ms |
6364 KB |
Output is correct |
| 39 |
Correct |
543 ms |
14200 KB |
Output is correct |
| 40 |
Correct |
542 ms |
14712 KB |
Output is correct |
| 41 |
Correct |
572 ms |
15860 KB |
Output is correct |
| 42 |
Correct |
513 ms |
13432 KB |
Output is correct |
| 43 |
Correct |
439 ms |
13504 KB |
Output is correct |
| 44 |
Correct |
717 ms |
19064 KB |
Output is correct |
| 45 |
Correct |
730 ms |
19080 KB |
Output is correct |
| 46 |
Correct |
685 ms |
19248 KB |
Output is correct |
| 47 |
Correct |
718 ms |
18824 KB |
Output is correct |
| 48 |
Correct |
741 ms |
19168 KB |
Output is correct |
| 49 |
Correct |
737 ms |
18808 KB |
Output is correct |
| 50 |
Correct |
771 ms |
19464 KB |
Output is correct |
