oj.uz

Submission #967319

# Submission time Handle Problem Language Result Execution time Memory
967319 2024-04-21T20:40:32 Z Keshav211 Rabbit Carrot (LMIO19_triusis) C++14
100 / 100
 102 ms 29640 KB 
#include <algorithm>
#include <fstream>
#include <iostream>
#include <vector>
#include <map>
#include <stack>
#include <queue>
#include <deque>
#include <set>
#include <chrono>
#include <string>
#include <numeric>
#include <cmath>
#include <iomanip>
#include <climits>
#include <bitset>
#define all(x) (x).begin(), (x).end()
#define vec(n) vll arr(n);
#define printarr(arr) for(auto i:arr){cout<<i<<" ";}cout<<endl;
#define printdict(dict) for(auto i:dict)cout<<i.first<<": "<<i.second<<endl;
#define printadj(adj) for(ll i=0;i<n;i++){if(!adj[i].empty()){cout<<i<<": ";printarr(adj[i])}}
#define read(arr); for(ll i=0;i<arr.size();i++) cin>>arr[i];
#define readundirected(m) for(ll i=0;i<m;i++){ll a,b; cin>>a>>b; a--;b--; adj[a].pb(b);adj[b].pb(a);}
#define readdirected(m) for(ll i=0;i<m;i++){ll a,b; cin>>a>>b; a--;b--; adj[a].pb(b);}
#define readfunc(n) for(ll i=0;i<n;i++){ll a;cin>>a;a--;func_adj[i]=a;}
#define grid(n,m) for (ll i=1;i<=n;i++){for (ll j=1;j<=m;j++) cin>>graph[i][j];}
#define vll vector<ll>
#define sll set<ll>
#define msll multiset<ll>
#define qll queue<ll>
#define pll pair<ll,ll>
#define str string
#define pb push_back
#define ll long long
#define ld long double
using namespace std;
const str alph="abcdefghijklmnopqrstuvwxyz";
const str capalph="ABCDEFGHIJKLMNOPQRSTUVWXYZ";
const ll inf=5e5+1;
const ll graph_size=1000;
const ll mod=1e9+7;
const ld pi=3.141592653589793238462643383279502884197;
const ll large=1e18;
const ll small=-1e18;
vll adj[inf];
bool visited[inf];
ll level[inf];
ll parent[inf];
char graph[graph_size+2][graph_size+2];
vector<pll> directions={{0,-1},{-1,0},{1,0},{0,1}};
bool floodfill_visited[graph_size+2][graph_size+2];
ll floodfill_level[graph_size+2][graph_size+2];
pll floodfill_parent[graph_size+2][graph_size+2];
// Fast Input/Output
void fastio(){
    ios_base::sync_with_stdio(0);
    cin.tie(nullptr);
}
// File Input/Output
str fileio(const string&filePath=__FILE__){
    size_t lastSlash=filePath.find_last_of('/');
    size_t lastDot=filePath.rfind('.');
    return filePath.substr(lastSlash+1,lastDot-lastSlash-1);
}
// For Yes Or No Problems
str yes_or_no(bool test){
    if (test){
       return "YES";
    }
    return "NO";
}
ll n,m,q;
// Coordinate Compression
vll compress(vll arr){
    map<ll,ll> count;
    for (auto i:arr){
        count[i]++;
    }
    ll curr=0;
    for (auto i:count){
        count[i.first]=curr;
        curr++;
    }
    for (ll i=0;i<arr.size();i++){
        arr[i]=count[arr[i]];
    }
    return arr;
}
// Segment Trees
struct segTree{
    vll tree;
    vll arr;
    const ll start_val=0;
    segTree(ll n){
        ll val=ceil(log2(n));
        n=1<<val;
        tree=vll(2*n,start_val);
        arr=vll(n,start_val);
    }
    ll merge(ll a,ll b){
        ll ans=max(a,b);
        return ans;
    }
    void add(ll ind,ll val){
        arr[ind]+=val;
        ind+=arr.size();
        tree[ind]+=val;
        while(ind/2>0){
            tree[ind/2]=merge(tree[ind],tree[ind^1]);
            ind/=2;
        }
    }
    void update(ll ind,ll val){
        add(ind,val-arr[ind]);
    }
    ll query(ll a,ll b){
        a+=arr.size();
        b+=arr.size();
        ll ans=start_val;
        while(a<=b){
            if(a%2==1){
                ans=merge(ans,tree[a]);
                a++;
            }
            if(b%2==0){
                ans=merge(ans,tree[b]);
                b--;
            }
            a/=2;
            b/=2;
        }
        return ans;
    }
};
int main(){
    // auto start_time=chrono::steady_clock::now();
    fastio();
    // str filename=fileio();
    // ifstream cin(filename+".in");
    // ofstream cout(filename+".out");
    ll t=1;
    // cin>>t;
    while (t--){
        cin>>n>>m;
        vll arr;
        for (ll i=0;i<n;i++){
            ll a;
            cin>>a;
            arr.pb(m*(i+1)-a);
            if (arr.back()<0){
                arr.pop_back();
            }
        }
        arr=compress(arr);
        segTree segtree(n);
        ll ans=0;
        for (auto i:arr){
            ll curr=segtree.query(0,i)+1;
            ans=max(ans,curr);
            segtree.update(i,max(segtree.arr[i],curr));
        }
        ans=n-ans;
        cout<<ans<<"\n";
    }
    // auto end_time=chrono::steady_clock::now();
    // auto elapsed_time=chrono::duration_cast<chrono::milliseconds>(end_time-start_time);
    // cout<<"Elapsed time: "<<elapsed_time.count()<<" milliseconds\n";
}

Compilation message

triusis.cpp: In function 'std::vector<long long int> compress(std::vector<long long int>)':
triusis.cpp:84:18: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   84 |     for (ll i=0;i<arr.size();i++){
      |                 ~^~~~~~~~~~~

Subtask #1
14.0 / 14.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14940 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 4 ms 15116 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 3 ms 12892 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 3 ms 12892 KB Output is correct
8 Correct 3 ms 12900 KB Output is correct
9 Correct 4 ms 12892 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 5 ms 12892 KB Output is correct
12 Correct 4 ms 12892 KB Output is correct
13 Correct 6 ms 12892 KB Output is correct
14 Correct 4 ms 12892 KB Output is correct
15 Correct 4 ms 12892 KB Output is correct
16 Correct 4 ms 12892 KB Output is correct

Subtask #2
21.0 / 21.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 14940 KB Output is correct
2 Correct 3 ms 14940 KB Output is correct
3 Correct 4 ms 15116 KB Output is correct
4 Correct 3 ms 12892 KB Output is correct
5 Correct 3 ms 12892 KB Output is correct
6 Correct 3 ms 12892 KB Output is correct
7 Correct 3 ms 12892 KB Output is correct
8 Correct 3 ms 12900 KB Output is correct
9 Correct 4 ms 12892 KB Output is correct
10 Correct 3 ms 12892 KB Output is correct
11 Correct 5 ms 12892 KB Output is correct
12 Correct 4 ms 12892 KB Output is correct
13 Correct 6 ms 12892 KB Output is correct
14 Correct 4 ms 12892 KB Output is correct
15 Correct 4 ms 12892 KB Output is correct
16 Correct 4 ms 12892 KB Output is correct
17 Correct 4 ms 12892 KB Output is correct
18 Correct 4 ms 12840 KB Output is correct
19 Correct 4 ms 13144 KB Output is correct
20 Correct 5 ms 13148 KB Output is correct
21 Correct 6 ms 13404 KB Output is correct
22 Correct 4 ms 13076 KB Output is correct
23 Correct 6 ms 13404 KB Output is correct
24 Correct 6 ms 13404 KB Output is correct
25 Correct 5 ms 13404 KB Output is correct
26 Correct 6 ms 13404 KB Output is correct
27 Correct 4 ms 13208 KB Output is correct
28 Correct 4 ms 13144 KB Output is correct
29 Correct 7 ms 13656 KB Output is correct
30 Correct 5 ms 13404 KB Output is correct
31 Correct 5 ms 13148 KB Output is correct
32 Correct 6 ms 13400 KB Output is correct
33 Correct 6 ms 13500 KB Output is correct

Subtask #3
28.0 / 28.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12892 KB Output is correct
2 Correct 4 ms 12840 KB Output is correct
3 Correct 4 ms 13144 KB Output is correct
4 Correct 5 ms 13148 KB Output is correct
5 Correct 6 ms 13404 KB Output is correct
6 Correct 4 ms 13076 KB Output is correct
7 Correct 6 ms 13404 KB Output is correct
8 Correct 6 ms 13404 KB Output is correct
9 Correct 5 ms 13404 KB Output is correct
10 Correct 6 ms 13404 KB Output is correct
11 Correct 4 ms 13208 KB Output is correct
12 Correct 4 ms 13144 KB Output is correct
13 Correct 7 ms 13656 KB Output is correct
14 Correct 5 ms 13404 KB Output is correct
15 Correct 5 ms 13148 KB Output is correct
16 Correct 6 ms 13400 KB Output is correct
17 Correct 6 ms 13500 KB Output is correct
18 Correct 7 ms 14940 KB Output is correct
19 Correct 3 ms 14940 KB Output is correct
20 Correct 4 ms 15116 KB Output is correct
21 Correct 3 ms 12892 KB Output is correct
22 Correct 3 ms 12892 KB Output is correct
23 Correct 3 ms 12892 KB Output is correct
24 Correct 3 ms 12892 KB Output is correct
25 Correct 3 ms 12900 KB Output is correct
26 Correct 4 ms 12892 KB Output is correct
27 Correct 3 ms 12892 KB Output is correct
28 Correct 5 ms 12892 KB Output is correct
29 Correct 4 ms 12892 KB Output is correct
30 Correct 6 ms 12892 KB Output is correct
31 Correct 4 ms 12892 KB Output is correct
32 Correct 4 ms 12892 KB Output is correct
33 Correct 4 ms 12892 KB Output is correct
34 Correct 4 ms 13196 KB Output is correct
35 Correct 4 ms 13148 KB Output is correct
36 Correct 4 ms 13200 KB Output is correct
37 Correct 5 ms 13404 KB Output is correct
38 Correct 4 ms 13148 KB Output is correct
39 Correct 5 ms 13136 KB Output is correct
40 Correct 5 ms 13148 KB Output is correct
41 Correct 4 ms 13144 KB Output is correct
42 Correct 6 ms 13404 KB Output is correct
43 Correct 6 ms 13336 KB Output is correct

Subtask #4
37.0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 13196 KB Output is correct
2 Correct 4 ms 13148 KB Output is correct
3 Correct 4 ms 13200 KB Output is correct
4 Correct 5 ms 13404 KB Output is correct
5 Correct 4 ms 13148 KB Output is correct
6 Correct 5 ms 13136 KB Output is correct
7 Correct 5 ms 13148 KB Output is correct
8 Correct 4 ms 13144 KB Output is correct
9 Correct 6 ms 13404 KB Output is correct
10 Correct 6 ms 13336 KB Output is correct
11 Correct 4 ms 12892 KB Output is correct
12 Correct 4 ms 12840 KB Output is correct
13 Correct 4 ms 13144 KB Output is correct
14 Correct 5 ms 13148 KB Output is correct
15 Correct 6 ms 13404 KB Output is correct
16 Correct 4 ms 13076 KB Output is correct
17 Correct 6 ms 13404 KB Output is correct
18 Correct 6 ms 13404 KB Output is correct
19 Correct 5 ms 13404 KB Output is correct
20 Correct 6 ms 13404 KB Output is correct
21 Correct 4 ms 13208 KB Output is correct
22 Correct 4 ms 13144 KB Output is correct
23 Correct 7 ms 13656 KB Output is correct
24 Correct 5 ms 13404 KB Output is correct
25 Correct 5 ms 13148 KB Output is correct
26 Correct 6 ms 13400 KB Output is correct
27 Correct 6 ms 13500 KB Output is correct
28 Correct 7 ms 14940 KB Output is correct
29 Correct 3 ms 14940 KB Output is correct
30 Correct 4 ms 15116 KB Output is correct
31 Correct 3 ms 12892 KB Output is correct
32 Correct 3 ms 12892 KB Output is correct
33 Correct 3 ms 12892 KB Output is correct
34 Correct 3 ms 12892 KB Output is correct
35 Correct 3 ms 12900 KB Output is correct
36 Correct 4 ms 12892 KB Output is correct
37 Correct 3 ms 12892 KB Output is correct
38 Correct 5 ms 12892 KB Output is correct
39 Correct 4 ms 12892 KB Output is correct
40 Correct 6 ms 12892 KB Output is correct
41 Correct 4 ms 12892 KB Output is correct
42 Correct 4 ms 12892 KB Output is correct
43 Correct 4 ms 12892 KB Output is correct
44 Correct 102 ms 28888 KB Output is correct
45 Correct 24 ms 21076 KB Output is correct
46 Correct 81 ms 22740 KB Output is correct
47 Correct 83 ms 22732 KB Output is correct
48 Correct 78 ms 29284 KB Output is correct
49 Correct 82 ms 29640 KB Output is correct
50 Correct 33 ms 22332 KB Output is correct
51 Correct 34 ms 22704 KB Output is correct
52 Correct 71 ms 23148 KB Output is correct
53 Correct 20 ms 20468 KB Output is correct
54 Correct 82 ms 29596 KB Output is correct
55 Correct 83 ms 29380 KB Output is correct