#include <bits/stdc++.h>
using namespace std;
void fast(){ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);}
int main(){
fast();
int n, m; cin>>n>>m;
int a[n+1]; a[0]=0;
for(int i=1; i<=n; i++){
cin>>a[i];
a[i]=m*i-a[i];
}
vector<int> v;
for(int i=1; i<=n; i++){
if(a[i]<0) continue;
int idx=upper_bound(v.begin(), v.end(), a[i])-v.begin();
if(idx==v.size()) v.push_back(a[i]);
else v[idx]=a[i];
}
cout<<n-v.size();
}
/*
const int N=1e5;
vector<int> v[N+1];
int lv[N+1];
int main(){
fast();
int n; cin>>n;
for(int i=1; i<n; i++){
int x, y; cin>>x>>y;
v[x].push_back(y);
v[y].push_back(x);
}
int ans=-1;
for(int i=1; i<=n; i++){
if()
}
}
*/
/*
const int N=24, NN=(1<<24), INF=1e9;
int last[NN+1], x[N+1], y[N+1], d[N+1][N+1];
int main(){
fast();
cin>>x[0]>>y[0];
int n; cin>>n;
for(int i=1; i<=n; i++) cin>>x[i]>>y[i];
for(int i=0; i<=n; i++){
for(int j=0; j<i; j++){
d[i][j]=d[j][i]=abs(x[i]-x[j])*abs(x[i]-x[j])+abs(y[i]-y[j])*abs(y[i]-y[j]);
}
}
int m=(1<<n);
vector<int> dp(NN, INF);
dp[0]=0;
for(int mask=0; mask<m; mask++){
if(dp[mask]==INF) continue;
for(int i=1; i<=n; i++){
if(mask&(1<<(i-1))) continue;
for(int j=1; j<=n; j++){
if(mask&(1<<(j-1))) continue;
int ii=(1<<(i-1)), jj=(1<<(j-1));
if(dp[mask|ii|jj]>dp[mask]+d[0][i]+d[i][j]+d[j][0]){
dp[mask|ii|jj]=dp[mask]+d[0][i]+d[i][j]+d[j][0];
last[mask|ii|jj]=mask;
}
}
break;
}
}
cout<<dp[m-1]<<'\n';
int bit=m-1;
vector<int> ans;
while(bit!=0){
int xo=bit^last[bit];
for(int i=0; i<n; i++){
if(xo&(1<<i)) ans.push_back(i+1);
}
ans.push_back(0);
bit=last[bit];
}
reverse(ans.begin(), ans.end());
for(auto i:ans) cout<<i<<' ';
cout<<0<<' ';
}
*/
/*
const int N=24, NN=(1<<24), INF=1e9;
int dp[NN+1], last[NN+1], x[N+1], y[N+1];
int main(){
fast();
cin>>x[0]>>y[0];
int n; cin>>n;
for(int i=1; i<=n; i++) cin>>x[i]>>y[i];
int m=(1<<n);
for(int i=1; i<m; i++) dp[i]=INF;
for(int i=1; i<=n; i++){
int add=0;
if(n==1) add=abs(x[0]-x[i])*abs(x[0]-x[i])+abs(y[0]-y[i])*abs(y[0]-y[i]);
dp[(1<<(i-1))]=abs(x[0]-x[i])*abs(x[0]-x[i])+abs(y[0]-y[i])*abs(y[0]-y[i])+add;
last[(1<<(i-1))]=i;
}
for(int mask=1; mask<m; mask++){
for(int i=1; i<=n; i++){
if(mask&((1<<(i-1)))) continue;
for(int j=1; j<=n; j++){
if(!(mask&((1<<(j-1))))) continue;
int add=0, nw=mask|(1<<(i-1));
if(nw==m-1){
add=abs(x[0]-x[i])*abs(x[0]-x[i])+abs(y[0]-y[i])*abs(y[0]-y[i]);
}
if(__builtin_popcount(mask)&1){
int ans=abs(x[i]-x[j])*abs(x[i]-x[j])+abs(y[i]-y[j])*abs(y[i]-y[j]);
if(dp[nw]>dp[mask]+ans+add){
dp[nw]=dp[mask]+ans+add;
last[nw]=i;
}
}
else{
int ans=abs(x[0]-x[i])*abs(x[0]-x[i])+abs(y[0]-y[i])*abs(y[0]-y[i]);
ans+=abs(x[0]-x[j])*abs(x[0]-x[j])+abs(y[0]-y[j])*abs(y[0]-y[j]);
if(dp[nw]>dp[mask]+ans+add){
dp[nw]=dp[mask]+ans+add;
last[nw]=i;
}
}
}
}
}
//for(int i=1; i<m; i++) cout<<last[i]<<'\n';
cout<<dp[m-1]<<'\n';
vector<int> ans;
int temp=m-1;
while(temp!=0){
ans.push_back(last[temp]);
temp^=(1<<(last[temp]-1));
}
reverse(ans.begin(), ans.end());
cout<<'0'<<' ';
for(int i=0; i<n; i++){
cout<<ans[i]<<' ';
if(i&1 || i==n-1) cout<<'0'<<' ';
}
}
*/
/*
const int N=3e5;
int freq[N+1][26], ans=0;
char c[N+1];
bool vis[N+1], to[N+1], cycle=false;
set<int> st;
vector<int> v[N+1];
void dfs(int node){
if(cycle) return;
st.insert(node);
freq[node][c[node]-'a']++;
vis[node]=true;
int frek[26];
memset(frek, 0, sizeof frek);
for(auto i:v[node]){
if(st.count(i)){
cycle=true;
return;
}
if(!vis[i]) dfs(i);
for(int j=0; j<26; j++) frek[j]=max(frek[j], freq[i][j]);
}
for(int i=0; i<26; i++){
freq[node][i]+=frek[i];
ans=max(ans, freq[node][i]);
}
st.erase(node);
}
int main(){
fast();
int n, m; cin>>n>>m;
for(int i=1; i<=n; i++) cin>>c[i];
for(int i=1; i<=m; i++){
int x, y; cin>>x>>y;
v[x].push_back(y);
to[y]=true;
}
for(int i=1; i<=n; i++){
if(!to[i]) dfs(i);
}
for(int i=1; i<=n; i++){
if(!vis[i]){
cycle=true;
break;
}
}
if(cycle) cout<<-1;
else cout<<ans;
}
*/
/*
#define int long long
const int N=1e6, mod=1e9+7;
int dp[N+1];
signed main(){
fast();
dp[0]=1;
int n, a; cin>>n;
priority_queue<int> pq;
for(int i=1; i<=n; i++){
cin>>a;
int root=sqrt(a);
for(int j=1; j<=root; j++){
if(a%j==0){
if(j!=a/j){
pq.push(j);
pq.push(a/j);
}
else pq.push(j);
}
}
while(!pq.empty()){
int u=pq.top(); pq.pop();
if(u<=i){
dp[u]=(dp[u]+dp[u-1])%mod;
}
}
}
int ans=0;
for(int i=1; i<=n; i++) ans=(ans+dp[i])%mod;
cout<<ans;
}
*/
/*
#define int long long
const int N=1e6, mod=998244353;
int fact[N+1], inv[N+1];
int expo(int a, int k){
int ret=1;
while(k){
if(k&1) ret=ret*a%mod;
a=a*a%mod;
k/=2;
}
return ret;
}
signed main(){
fast();
fact[0]=fact[1]=1;
for(int i=2; i<=N; i++) fact[i]=fact[i-1]*i%mod;
inv[N]=expo(fact[N], mod-2);
for(int i=N-1; i>=0; i--) inv[i]=inv[i+1]*(i+1)%mod;
int n; cin>>n;
int ans=fact[n];
for(int i=1; i<=n-2; i++) ans=(ans+(fact[n-i]-1)*fact[n]%mod*inv[n-i]%mod)%mod;
cout<<ans;
}
*/
/*
const int N=1e3, mx=2520;
int n, timer, a[N+1], b[N+1], sz[N+1], dp[N+1][mx+1];
vector<vector<int>> v(N+1);
int dfs(int x, int y){
if(dp[x][y]>0) return dp[x][y];
if(dp[x][y]<0){
int sum=0;
for(int i=1; i<=n; i++){
if(b[i]<=dp[x][y]) sum++;
}
return dp[x][y]=sum;
}
dp[x][y]=b[x]=--timer;
return dp[x][y]=dfs(v[x][(y+a[x])%sz[x]], (y+a[x])%mx);
}
int main(){
cin>>n;
for(int i=1; i<=n; i++){
cin>>a[i];
a[i]=((a[i]%mx)+mx)%mx;
}
int x, y;
for(int i=1; i<=n; i++){
cin>>sz[i];
for(int j=0; j<sz[i]; j++){
cin>>x;
v[i].push_back(x);
}
}
int q; cin>>q;
while(q--){
cin>>x>>y;
cout<<dfs(x, (y%mx+mx)%mx)<<'\n';
}
}*/
Compilation message
triusis.cpp: In function 'int main()':
triusis.cpp:17:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | if(idx==v.size()) v.push_back(a[i]);
| ~~~^~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
320 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
320 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
316 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
316 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
320 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
0 ms |
212 KB |
Output is correct |
8 |
Correct |
0 ms |
212 KB |
Output is correct |
9 |
Correct |
0 ms |
212 KB |
Output is correct |
10 |
Correct |
1 ms |
320 KB |
Output is correct |
11 |
Correct |
0 ms |
212 KB |
Output is correct |
12 |
Correct |
1 ms |
212 KB |
Output is correct |
13 |
Correct |
0 ms |
212 KB |
Output is correct |
14 |
Correct |
1 ms |
316 KB |
Output is correct |
15 |
Correct |
1 ms |
212 KB |
Output is correct |
16 |
Correct |
1 ms |
316 KB |
Output is correct |
17 |
Correct |
1 ms |
212 KB |
Output is correct |
18 |
Correct |
0 ms |
320 KB |
Output is correct |
19 |
Correct |
1 ms |
320 KB |
Output is correct |
20 |
Correct |
1 ms |
328 KB |
Output is correct |
21 |
Correct |
1 ms |
328 KB |
Output is correct |
22 |
Correct |
1 ms |
340 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
332 KB |
Output is correct |
28 |
Correct |
1 ms |
328 KB |
Output is correct |
29 |
Correct |
1 ms |
340 KB |
Output is correct |
30 |
Correct |
1 ms |
340 KB |
Output is correct |
31 |
Correct |
1 ms |
340 KB |
Output is correct |
32 |
Correct |
1 ms |
340 KB |
Output is correct |
33 |
Correct |
1 ms |
328 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
320 KB |
Output is correct |
3 |
Correct |
1 ms |
320 KB |
Output is correct |
4 |
Correct |
1 ms |
328 KB |
Output is correct |
5 |
Correct |
1 ms |
328 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
340 KB |
Output is correct |
11 |
Correct |
1 ms |
332 KB |
Output is correct |
12 |
Correct |
1 ms |
328 KB |
Output is correct |
13 |
Correct |
1 ms |
340 KB |
Output is correct |
14 |
Correct |
1 ms |
340 KB |
Output is correct |
15 |
Correct |
1 ms |
340 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
328 KB |
Output is correct |
18 |
Correct |
1 ms |
212 KB |
Output is correct |
19 |
Correct |
0 ms |
212 KB |
Output is correct |
20 |
Correct |
0 ms |
212 KB |
Output is correct |
21 |
Correct |
0 ms |
212 KB |
Output is correct |
22 |
Correct |
1 ms |
320 KB |
Output is correct |
23 |
Correct |
0 ms |
212 KB |
Output is correct |
24 |
Correct |
0 ms |
212 KB |
Output is correct |
25 |
Correct |
0 ms |
212 KB |
Output is correct |
26 |
Correct |
0 ms |
212 KB |
Output is correct |
27 |
Correct |
1 ms |
320 KB |
Output is correct |
28 |
Correct |
0 ms |
212 KB |
Output is correct |
29 |
Correct |
1 ms |
212 KB |
Output is correct |
30 |
Correct |
0 ms |
212 KB |
Output is correct |
31 |
Correct |
1 ms |
316 KB |
Output is correct |
32 |
Correct |
1 ms |
212 KB |
Output is correct |
33 |
Correct |
1 ms |
316 KB |
Output is correct |
34 |
Correct |
1 ms |
328 KB |
Output is correct |
35 |
Correct |
1 ms |
340 KB |
Output is correct |
36 |
Correct |
1 ms |
340 KB |
Output is correct |
37 |
Correct |
1 ms |
344 KB |
Output is correct |
38 |
Correct |
1 ms |
332 KB |
Output is correct |
39 |
Correct |
1 ms |
340 KB |
Output is correct |
40 |
Correct |
1 ms |
340 KB |
Output is correct |
41 |
Correct |
1 ms |
340 KB |
Output is correct |
42 |
Correct |
1 ms |
340 KB |
Output is correct |
43 |
Correct |
1 ms |
328 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
1 ms |
328 KB |
Output is correct |
2 |
Correct |
1 ms |
340 KB |
Output is correct |
3 |
Correct |
1 ms |
340 KB |
Output is correct |
4 |
Correct |
1 ms |
344 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
1 ms |
340 KB |
Output is correct |
7 |
Correct |
1 ms |
340 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
1 ms |
340 KB |
Output is correct |
10 |
Correct |
1 ms |
328 KB |
Output is correct |
11 |
Correct |
1 ms |
212 KB |
Output is correct |
12 |
Correct |
0 ms |
320 KB |
Output is correct |
13 |
Correct |
1 ms |
320 KB |
Output is correct |
14 |
Correct |
1 ms |
328 KB |
Output is correct |
15 |
Correct |
1 ms |
328 KB |
Output is correct |
16 |
Correct |
1 ms |
340 KB |
Output is correct |
17 |
Correct |
1 ms |
340 KB |
Output is correct |
18 |
Correct |
1 ms |
340 KB |
Output is correct |
19 |
Correct |
1 ms |
340 KB |
Output is correct |
20 |
Correct |
1 ms |
340 KB |
Output is correct |
21 |
Correct |
1 ms |
332 KB |
Output is correct |
22 |
Correct |
1 ms |
328 KB |
Output is correct |
23 |
Correct |
1 ms |
340 KB |
Output is correct |
24 |
Correct |
1 ms |
340 KB |
Output is correct |
25 |
Correct |
1 ms |
340 KB |
Output is correct |
26 |
Correct |
1 ms |
340 KB |
Output is correct |
27 |
Correct |
1 ms |
328 KB |
Output is correct |
28 |
Correct |
1 ms |
212 KB |
Output is correct |
29 |
Correct |
0 ms |
212 KB |
Output is correct |
30 |
Correct |
0 ms |
212 KB |
Output is correct |
31 |
Correct |
0 ms |
212 KB |
Output is correct |
32 |
Correct |
1 ms |
320 KB |
Output is correct |
33 |
Correct |
0 ms |
212 KB |
Output is correct |
34 |
Correct |
0 ms |
212 KB |
Output is correct |
35 |
Correct |
0 ms |
212 KB |
Output is correct |
36 |
Correct |
0 ms |
212 KB |
Output is correct |
37 |
Correct |
1 ms |
320 KB |
Output is correct |
38 |
Correct |
0 ms |
212 KB |
Output is correct |
39 |
Correct |
1 ms |
212 KB |
Output is correct |
40 |
Correct |
0 ms |
212 KB |
Output is correct |
41 |
Correct |
1 ms |
316 KB |
Output is correct |
42 |
Correct |
1 ms |
212 KB |
Output is correct |
43 |
Correct |
1 ms |
316 KB |
Output is correct |
44 |
Correct |
12 ms |
2644 KB |
Output is correct |
45 |
Correct |
16 ms |
2992 KB |
Output is correct |
46 |
Correct |
23 ms |
3028 KB |
Output is correct |
47 |
Correct |
22 ms |
3148 KB |
Output is correct |
48 |
Correct |
15 ms |
3128 KB |
Output is correct |
49 |
Correct |
16 ms |
3384 KB |
Output is correct |
50 |
Correct |
19 ms |
3676 KB |
Output is correct |
51 |
Correct |
19 ms |
4156 KB |
Output is correct |
52 |
Correct |
17 ms |
2520 KB |
Output is correct |
53 |
Correct |
13 ms |
2336 KB |
Output is correct |
54 |
Correct |
16 ms |
3256 KB |
Output is correct |
55 |
Correct |
16 ms |
3256 KB |
Output is correct |