oj.uz

답안 #466172

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
466172 2021-08-18T09:18:01 Z sinamhdv LIS (INOI20_lis) C++11
20 / 100
 4000 ms 4380 KB 
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int mod = 1000 * 1000 * 1000 + 7;
const int INF = 1e9 + 100;
const ll LINF = 1e18 + 100;

#ifdef DEBUG
#define dbg(x) cout << #x << " = " << (x) << endl << flush;
#define dbgr(s, f) { cout << #s << ": "; for (auto _ = (s); _ != (f); _++) cout << *_ << ' '; cout << endl << flush; }
#else
#define dbg(x) ;
#define dbgr(s, f) ;
#endif
#define FOR(i, a, b) for (int i = (a); i < (b); i++)
#define fast_io ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define pb push_back
#define fr first
#define sc second
#define all(x) (x).begin(), (x).end()
#define endl '\n'

const int MAXN = 1000100;

int n, p[MAXN], x[MAXN];
vector<int> vec;
int dp[MAXN];

inline int getlis(void)
{
	fill(dp, dp + MAXN, INF);
	dp[0] = -INF;
	for (int u : vec)
	{
		int pos = lower_bound(dp, dp + MAXN, u) - dp;
		dp[pos] = u;
	}
	int ans = lower_bound(dp, dp + MAXN, INF) - dp - 1;
	return ans;
}

int32_t main(void)
{
	fast_io;
	cin >> n;
	FOR(i, 0, n)
	{
		cin >> p[i] >> x[i];
		p[i]--;
		vec.insert(vec.begin() + p[i], x[i]);
		cout << getlis() << endl;
	}
	return 0;
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4172 KB Output is correct
2 Correct 6 ms 4172 KB Output is correct
3 Correct 1101 ms 4232 KB Output is correct
4 Correct 1110 ms 4292 KB Output is correct
5 Correct 1046 ms 4264 KB Output is correct
6 Correct 1148 ms 4252 KB Output is correct
7 Correct 1044 ms 4260 KB Output is correct
8 Correct 1057 ms 4260 KB Output is correct
9 Correct 1142 ms 4300 KB Output is correct
10 Correct 1211 ms 4244 KB Output is correct
11 Correct 1126 ms 4252 KB Output is correct
12 Correct 1200 ms 4228 KB Output is correct
13 Correct 1208 ms 4260 KB Output is correct
14 Correct 1191 ms 4252 KB Output is correct
15 Correct 1081 ms 4256 KB Output is correct
16 Correct 1128 ms 4368 KB Output is correct
17 Correct 1141 ms 4260 KB Output is correct
18 Correct 1095 ms 4292 KB Output is correct

Subtask #2
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 4172 KB Output is correct
2 Correct 6 ms 4172 KB Output is correct
3 Correct 1101 ms 4232 KB Output is correct
4 Correct 1110 ms 4292 KB Output is correct
5 Correct 1046 ms 4264 KB Output is correct
6 Correct 1148 ms 4252 KB Output is correct
7 Correct 1044 ms 4260 KB Output is correct
8 Correct 1057 ms 4260 KB Output is correct
9 Correct 1142 ms 4300 KB Output is correct
10 Correct 1211 ms 4244 KB Output is correct
11 Correct 1126 ms 4252 KB Output is correct
12 Correct 1200 ms 4228 KB Output is correct
13 Correct 1208 ms 4260 KB Output is correct
14 Correct 1191 ms 4252 KB Output is correct
15 Correct 1081 ms 4256 KB Output is correct
16 Correct 1128 ms 4368 KB Output is correct
17 Correct 1141 ms 4260 KB Output is correct
18 Correct 1095 ms 4292 KB Output is correct
19 Execution timed out 4035 ms 4380 KB Time limit exceeded
20 Halted 0 ms 0 KB -