Submission #3768250
Source Code Expand
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#include <climits>
#define rep(i, m, n) for(int i=int(m);i<int(n);i++)
#define all(c) begin(c),end(c)
template<typename T1, typename T2>
inline void chmin(T1 &a, T2 b) { if (a > b) a = b; }
template<typename T1, typename T2>
inline void chmax(T1 &a, T2 b) { if (a < b) a = b; }
//改造
typedef long long int ll;
using namespace std;
#define INF (1 << 30) - 1
#define INFl (ll)5e15
#define DEBUG 0 //デバッグする時1にしてね
#define dump(x) cerr << #x << " = " << (x) << endl
#define MOD 1000000007
//ここから編集する
class SegTree {
public:
const int MAX_N = 1 << 17;
int n;
vector<ll> dat;
const ll INITIAL_DAT = 0L;
SegTree(int n_) {
init(n_);
}
void init(int n_) {
n = 1;
while (n < n_) n *= 2;
dat = vector<ll>(2 * n);
for (int i = 0; i < 2 * n - 1; ++i) dat[i] = INITIAL_DAT;
}
//どんなSegTreeを構築するか(デフォルトはRMQ)
ll calc(ll vl, ll vr) {
return max(vl, vr);
}
//k番目の値(0-indexed)をaに変更
void update(int k, ll a) {
k += n - 1;
dat[k] = a;
//登りながら更新
while (k > 0) {
k = (k - 1) / 2;
// dat[k] = min(dat[k * 2 + 1], dat[k * 2 + 2]);
dat[k] = calc(dat[k * 2 + 1], dat[k * 2 + 2]);
}
}
//[a,b)の最小値を求める
//kは接点の番号,l,rはその接点が[l,r)に対応づいていることを表す。
//したがって、外からはquery(a,b,0,0,n)として呼ぶ。
ll query(int a, int b, int k, int l, int r) {
//[a,b)と[l,r)が交差しなければINITIAL_DAT
if (r <= a || b <= l) return INITIAL_DAT;
//[a,b)が[l,r)が交差しなければ、INT_MAX
if (a <= l && r <= b) return dat[k];
else {
//そうでなければ、2つの子に対する処理,デフォルトは最小値
ll vl = query(a, b, k * 2 + 1, l, (l + r) / 2);
ll vr = query(a, b, k * 2 + 2, (l + r) / 2, r);
return calc(vl, vr);
}
}
//[a,b)の最小値を求める
ll find(int a, int b) {
return query(a, b, 0, 0, n);
}
};
class Solve {
public:
void input() {
}
void solve() {
input();
const int max_v = 123456;
vector<vector<int>> vv(max_v);
int N;
cin >> N;
for (int i = 0; i < N; ++i) {
int h, w;
cin >> h >> w;
vv[h].push_back(w);
}
for (int i = 0; i < max_v; ++i) {
sort(vv[i].rbegin(), vv[i].rend());
}
SegTree treeone(max_v);
for (int i = 1; i < max_v; ++i) {
for (auto e : vv[i]) {
ll tmp = treeone.find(0, e);
treeone.update(e, tmp + 1);
}
}
ll ans = treeone.find(0,max_v);
cout << ans << endl;
}
};
int main() {
cin.tie(0);
ios::sync_with_stdio(false);
Solve().solve();
return 0;
}
Submission Info
Submission Time |
|
Task |
D - プレゼント |
User |
homesentinel |
Language |
C++14 (Clang 3.8.0) |
Score |
100 |
Code Size |
3786 Byte |
Status |
AC |
Exec Time |
194 ms |
Memory |
8320 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 |
5 ms |
5248 KB |
sample1.txt |
AC |
5 ms |
5248 KB |
sample2.txt |
AC |
4 ms |
5248 KB |
sample3.txt |
AC |
5 ms |
5248 KB |
subtask0_0.txt |
AC |
6 ms |
5248 KB |
subtask0_1.txt |
AC |
5 ms |
5248 KB |
subtask0_10.txt |
AC |
6 ms |
5248 KB |
subtask0_11.txt |
AC |
6 ms |
5248 KB |
subtask0_12.txt |
AC |
6 ms |
5248 KB |
subtask0_13.txt |
AC |
6 ms |
5248 KB |
subtask0_14.txt |
AC |
7 ms |
5248 KB |
subtask0_2.txt |
AC |
5 ms |
5248 KB |
subtask0_3.txt |
AC |
5 ms |
5248 KB |
subtask0_4.txt |
AC |
6 ms |
5248 KB |
subtask0_5.txt |
AC |
5 ms |
5248 KB |
subtask0_6.txt |
AC |
6 ms |
5248 KB |
subtask0_7.txt |
AC |
7 ms |
5248 KB |
subtask0_8.txt |
AC |
6 ms |
5248 KB |
subtask0_9.txt |
AC |
6 ms |
5248 KB |
subtask1_0.txt |
AC |
119 ms |
6656 KB |
subtask1_1.txt |
AC |
8 ms |
5248 KB |
subtask1_10.txt |
AC |
175 ms |
8320 KB |
subtask1_11.txt |
AC |
177 ms |
8320 KB |
subtask1_12.txt |
AC |
192 ms |
7168 KB |
subtask1_13.txt |
AC |
191 ms |
7168 KB |
subtask1_14.txt |
AC |
194 ms |
7168 KB |
subtask1_2.txt |
AC |
35 ms |
5632 KB |
subtask1_3.txt |
AC |
164 ms |
7040 KB |
subtask1_4.txt |
AC |
192 ms |
7168 KB |
subtask1_5.txt |
AC |
32 ms |
5632 KB |
subtask1_6.txt |
AC |
144 ms |
6784 KB |
subtask1_7.txt |
AC |
83 ms |
6272 KB |
subtask1_8.txt |
AC |
168 ms |
7040 KB |
subtask1_9.txt |
AC |
89 ms |
6272 KB |