Submission #3768003
Source Code Expand
// warm heart, wagging tail,and a smile just for you!
// ███████████
// ███╬╬╬╬╬╬╬╬╬╬███
// ███╬╬╬╬╬╬╬██╬╬╬╬╬╬███
// ███████████ ██╬╬╬╬╬████╬╬████╬╬╬╬╬██
// █████████╬╬╬╬╬████████████╬╬╬╬╬██╬╬╬╬╬╬███╬╬╬╬╬██
// ████████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████████╬╬╬╬╬╬██╬╬╬╬╬╬╬██
// ████╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████████╬╬╬╬╬╬╬╬╬╬╬██
// ███╬╬╬█╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬███╬╬╬╬╬╬╬█████
// ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬████████╬╬╬╬╬██
// ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬╬╬╬╬╬╬╬███
// ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬██
// ████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████╬╬╬╬╬████
// █████████████╬╬╬╬╬╬╬╬██╬╬╬╬╬████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬╬╬██████
// ████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬██████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██████╬╬╬╬╬╬╬███████████╬╬╬╬╬╬╬╬██╬╬╬██╬╬╬██
// ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████╬╬╬╬╬╬╬╬╬╬╬█╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬██
// ██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬▓▓▓▓▓▓╬╬╬████╬╬████╬╬╬╬╬╬╬▓▓▓▓▓▓▓▓▓█╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬███
// ██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██████▓▓▓▓▓▓▓╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬▓▓▓▓▓▓▓▓█╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██╬╬╬╬█████
// ███╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████████
// ███╬╬╬╬╬╬╬╬╬╬╬╬╬█████╬╬╬╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬███╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬██
// ██████████████ ████╬╬╬╬╬╬███████████████████████████╬╬╬╬╬██╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬╬████
// ███████ █████ ███████████████████
#include "bits/stdc++.h"
using namespace std;
#define MOD 1000000007
#define INF 1LL<<60
#define fs first
#define sc second
#define pb push_back
#define int long long
#define FOR(i,a,b) for(int i=(a);i<(b);i++)
#define RFOR(i,a,b) for(int i = (b-1);i>=a;i--)
#define REP(i,n) FOR(i,0,n)
#define RREP(i,n) RFOR(i,0,n)
#define ITR(itr,mp) for(auto itr = (mp).begin(); itr != (mp).end(); ++itr)
#define RITR(itr,mp) for(auto itr = (mp).rbegin(); itr != (mp).rend(); ++itr)
#define debug(x) cout << #x << " = " << (x) << endl;
typedef pair<int,int> P;
typedef vector<vector<P>> Graph;
int MAX_N = 1e5,num = 1e5;
vector<int> bit(MAX_N+1,0);
int maxi(int i){
int s = 0;
while(i > 0){
s = max(s,bit[i]);
i -= i & -i;
}
return s;
}
void add(int i, int x){
while(i <= num){
bit[i] = max(bit[i],x);
i += i & -i;
}
}
bool org(P x, P y){
if(x.fs != y.fs) return x.fs < y.fs;
else return x.sc > y.sc;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
vector<P> size(n);
REP(i,n){
int x,y;
cin >> x >> y;
size[i] = P(x,y);
}
sort(size.begin(),size.end(),org);
vector<int> dp(n);
int ans = 0;
REP(i,n){
dp[i] = maxi(size[i].sc-1)+1;
add(size[i].sc,dp[i]);
ans = max(dp[i],ans);
}
cout << ans << endl;
return 0;
}
Submission Info
Submission Time |
|
Task |
D - プレゼント |
User |
cinnamoroll |
Language |
C++14 (GCC 5.4.1) |
Score |
100 |
Code Size |
6222 Byte |
Status |
AC |
Exec Time |
31 ms |
Memory |
3456 KB |
Judge Result
Set Name |
Sample |
Subtask0 |
All |
Score / Max Score |
0 / 0 |
30 / 30 |
70 / 70 |
Status |
|
|
|
Set Name |
Test Cases |
Sample |
sample0.txt, sample1.txt, sample2.txt, sample3.txt |
Subtask0 |
subtask0_0.txt, subtask0_1.txt, subtask0_10.txt, subtask0_11.txt, subtask0_12.txt, subtask0_13.txt, subtask0_14.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt, sample0.txt, sample1.txt, sample2.txt, sample3.txt |
All |
sample0.txt, sample1.txt, sample2.txt, sample3.txt, subtask0_0.txt, subtask0_1.txt, subtask0_10.txt, subtask0_11.txt, subtask0_12.txt, subtask0_13.txt, subtask0_14.txt, subtask0_2.txt, subtask0_3.txt, subtask0_4.txt, subtask0_5.txt, subtask0_6.txt, subtask0_7.txt, subtask0_8.txt, subtask0_9.txt, subtask1_0.txt, subtask1_1.txt, subtask1_10.txt, subtask1_11.txt, subtask1_12.txt, subtask1_13.txt, subtask1_14.txt, subtask1_2.txt, subtask1_3.txt, subtask1_4.txt, subtask1_5.txt, subtask1_6.txt, subtask1_7.txt, subtask1_8.txt, subtask1_9.txt |
Case Name |
Status |
Exec Time |
Memory |
sample0.txt |
AC |
2 ms |
1024 KB |
sample1.txt |
AC |
2 ms |
1024 KB |
sample2.txt |
AC |
2 ms |
1024 KB |
sample3.txt |
AC |
2 ms |
1024 KB |
subtask0_0.txt |
AC |
2 ms |
1024 KB |
subtask0_1.txt |
AC |
2 ms |
1024 KB |
subtask0_10.txt |
AC |
2 ms |
1024 KB |
subtask0_11.txt |
AC |
2 ms |
1024 KB |
subtask0_12.txt |
AC |
2 ms |
1024 KB |
subtask0_13.txt |
AC |
2 ms |
1024 KB |
subtask0_14.txt |
AC |
2 ms |
1024 KB |
subtask0_2.txt |
AC |
2 ms |
1024 KB |
subtask0_3.txt |
AC |
2 ms |
1024 KB |
subtask0_4.txt |
AC |
2 ms |
1024 KB |
subtask0_5.txt |
AC |
2 ms |
1024 KB |
subtask0_6.txt |
AC |
2 ms |
1024 KB |
subtask0_7.txt |
AC |
2 ms |
1024 KB |
subtask0_8.txt |
AC |
2 ms |
1024 KB |
subtask0_9.txt |
AC |
2 ms |
1024 KB |
subtask1_0.txt |
AC |
20 ms |
2432 KB |
subtask1_1.txt |
AC |
2 ms |
1152 KB |
subtask1_10.txt |
AC |
25 ms |
3456 KB |
subtask1_11.txt |
AC |
24 ms |
3456 KB |
subtask1_12.txt |
AC |
31 ms |
3456 KB |
subtask1_13.txt |
AC |
31 ms |
3456 KB |
subtask1_14.txt |
AC |
31 ms |
3456 KB |
subtask1_2.txt |
AC |
6 ms |
1408 KB |
subtask1_3.txt |
AC |
27 ms |
3072 KB |
subtask1_4.txt |
AC |
31 ms |
3328 KB |
subtask1_5.txt |
AC |
6 ms |
1408 KB |
subtask1_6.txt |
AC |
24 ms |
2816 KB |
subtask1_7.txt |
AC |
13 ms |
2048 KB |
subtask1_8.txt |
AC |
27 ms |
3072 KB |
subtask1_9.txt |
AC |
14 ms |
2048 KB |