oj.uz

답안 #469488

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
469488 2021-09-01T06:33:50 Z radal LIS (INOI20_lis) C++14
20 / 100
 4000 ms 4628 KB 
#include <bits/stdc++.h>
#pragma GCC target ("avx,avx2,fma")
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
#define X first
#define Y second
#define debug(x) cerr << #x << ": " << x << endl;
#define endl '\n'
#define pb push_back
#define rep(i,l,r) for (int i=l; i<r; i++)
#define repr(i,r,l) for (int i=r; i>=l; i--)
using namespace std;
typedef long long ll;
typedef pair<int,int> pll;
const long long int N = 1e6+20,mod = 1e9+7,inf=1e9+1;
int lis[N],a[N],b[N];
int main(){
    ios :: sync_with_stdio(0); cin.tie(0); cout.tie(0);
    int q;
    cin >> q;
    rep(j,1,q+1){
        memset(lis,63,sizeof lis);
        lis[0] = 0;
        int p,x;
        cin >> p >> x;
        rep(i,1,p)
            b[i] = a[i];
        b[p] = x;
        rep(i,p+1,j+1)
            b[i] = a[i-1];
        int ans = 0;
        rep(i,1,j+1){
            a[i] = b[i];
            int ind = lower_bound(lis,lis+j+1,a[i])-lis;
            lis[ind] = a[i];
            ans = max(ans,ind);
        }
        cout << ans << endl;
    }
}

Subtask #1
20.0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4172 KB Output is correct
2 Correct 3 ms 4172 KB Output is correct
3 Correct 329 ms 4240 KB Output is correct
4 Correct 349 ms 4240 KB Output is correct
5 Correct 299 ms 4248 KB Output is correct
6 Correct 342 ms 4232 KB Output is correct
7 Correct 313 ms 4240 KB Output is correct
8 Correct 305 ms 4296 KB Output is correct
9 Correct 322 ms 4356 KB Output is correct
10 Correct 310 ms 4172 KB Output is correct
11 Correct 298 ms 4236 KB Output is correct
12 Correct 330 ms 4240 KB Output is correct
13 Correct 350 ms 4420 KB Output is correct
14 Correct 336 ms 4292 KB Output is correct
15 Correct 337 ms 4244 KB Output is correct
16 Correct 344 ms 4432 KB Output is correct
17 Correct 339 ms 4248 KB Output is correct
18 Correct 335 ms 4244 KB Output is correct

Subtask #2
0 / 80.0

# 결과 실행 시간 메모리 Grader output
1 Correct 3 ms 4172 KB Output is correct
2 Correct 3 ms 4172 KB Output is correct
3 Correct 329 ms 4240 KB Output is correct
4 Correct 349 ms 4240 KB Output is correct
5 Correct 299 ms 4248 KB Output is correct
6 Correct 342 ms 4232 KB Output is correct
7 Correct 313 ms 4240 KB Output is correct
8 Correct 305 ms 4296 KB Output is correct
9 Correct 322 ms 4356 KB Output is correct
10 Correct 310 ms 4172 KB Output is correct
11 Correct 298 ms 4236 KB Output is correct
12 Correct 330 ms 4240 KB Output is correct
13 Correct 350 ms 4420 KB Output is correct
14 Correct 336 ms 4292 KB Output is correct
15 Correct 337 ms 4244 KB Output is correct
16 Correct 344 ms 4432 KB Output is correct
17 Correct 339 ms 4248 KB Output is correct
18 Correct 335 ms 4244 KB Output is correct
19 Execution timed out 4067 ms 4628 KB Time limit exceeded
20 Halted 0 ms 0 KB -