Submission #469487

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
469487	2021-09-01T06:32:38 Z	radal	LIS (INOI20_lis)	C++14	20 / 100	102 ms	576 KB

Main

#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 = 2e3+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

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	27 ms	452 KB	Output is correct
4	Correct	61 ms	332 KB	Output is correct
5	Correct	27 ms	352 KB	Output is correct
6	Correct	60 ms	332 KB	Output is correct
7	Correct	30 ms	340 KB	Output is correct
8	Correct	30 ms	352 KB	Output is correct
9	Correct	32 ms	332 KB	Output is correct
10	Correct	29 ms	332 KB	Output is correct
11	Correct	32 ms	332 KB	Output is correct
12	Correct	60 ms	340 KB	Output is correct
13	Correct	63 ms	332 KB	Output is correct
14	Correct	63 ms	332 KB	Output is correct
15	Correct	61 ms	348 KB	Output is correct
16	Correct	63 ms	332 KB	Output is correct
17	Correct	64 ms	332 KB	Output is correct
18	Correct	65 ms	352 KB	Output is correct

Subtask #2

0 / 80.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	1 ms	332 KB	Output is correct
2	Correct	0 ms	204 KB	Output is correct
3	Correct	27 ms	452 KB	Output is correct
4	Correct	61 ms	332 KB	Output is correct
5	Correct	27 ms	352 KB	Output is correct
6	Correct	60 ms	332 KB	Output is correct
7	Correct	30 ms	340 KB	Output is correct
8	Correct	30 ms	352 KB	Output is correct
9	Correct	32 ms	332 KB	Output is correct
10	Correct	29 ms	332 KB	Output is correct
11	Correct	32 ms	332 KB	Output is correct
12	Correct	60 ms	340 KB	Output is correct
13	Correct	63 ms	332 KB	Output is correct
14	Correct	63 ms	332 KB	Output is correct
15	Correct	61 ms	348 KB	Output is correct
16	Correct	63 ms	332 KB	Output is correct
17	Correct	64 ms	332 KB	Output is correct
18	Correct	65 ms	352 KB	Output is correct
19	Runtime error	102 ms	576 KB	Execution killed with signal 11
20	Halted	0 ms	0 KB	-