Submission #469488

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
469488	2021-09-01T06:33:50 Z	radal	LIS (INOI20_lis)	C++14	20 / 100	4000 ms	4628 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 = 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

#	Verdict	Execution time	Memory	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

#	Verdict	Execution time	Memory	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	-