Submission #423521

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
423521	2021-06-11T08:35:25 Z	장태환(#7573)	Monster Game (JOI21_monster)	C++17	Compilation error	0 ms	0 KB

monster

#include <bits/stdc++.h>
using namespace std;
struct stree
{
    int st[600100];
    int N;
    void init(vector<int>arr)
    {
        N=arr.size();
        int i;
        for(i=0;i<N;i++)
            st[i+N]=arr[i];
        for(i=N-1;i>0;i--)
            st[i]=max(st[i<<1],st[i<<1|1]);
    }
    void upd(int n,int k)
    {
        st[N+n]=k;
        for(n+=N;n>1;n>>=1)
        {
            st[n>>1]=max(st[n],st[n^1]);
        }
    }
    int q(int l,int r,int mi)
    {
        int ans=mi;
        l+=N;
        r+=N;
        for(;l<r;l>>=1,r>>=1)
        {
            if(l&1)
                ans=max(ans,st[l++]);
            if(r&1)
                ans=max(ans,st[--r]);

        }
        return ans;
    }
}val,cma,dp;
string s[3];
int lim[300100];
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int N,M;
    cin >> N >> M;
    M--;
    int i;
    vector<pair<int,int>>x;
    vector<int>arr;
    vector<int>da(N,0);
    dp.init(da);
    for(i=0;i<N;i++)
    {
        int a;
        cin >> a;
        x.push_back({-a,i});
        arr.push_back(-a);
    }
    sort(x.begin(),x.end());
    val.init(arr);
    vector<int>su;
    for(i=0;i<N-M;i++)
    {
        su.push_back(-val.q(i,i+M+1,-(1<<30)));
    }
    cma.init(su);
    for(i=0;i<N;i++)
    {
        int s=i+1;
        int e=su.size();
        while(s<e)
        {
            int m=(s+e)>>1;
            if(cma.q(i+1,m+1,0)<=-arr[i])
                s=m+1;
            else
                e=m;
        }
        if(e==su.size())
            lim[i]=N;
        lim[i]=e+M+1;
    }
    int ans=0;
    for(i=0;i<N;i++)
    {
        int va=dp.q(x[i].second+1,lim[x[i].second],0)+1;
        ans=max(ans,va);
        dp.upd(x[i].second,va);
    }
    cout << ans;
}

Compilation message

monster.cpp: In function 'int main()':
monster.cpp:81:13: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   81 |         if(e==su.size())
      |            ~^~~~~~~~~~~
/usr/bin/ld: /tmp/cc0CTFdk.o: in function `main':
stub.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccH20Skk.o:monster.cpp:(.text.startup+0x0): first defined here
/usr/bin/ld: /tmp/cc0CTFdk.o: in function `main':
stub.cpp:(.text.startup+0xb3): undefined reference to `Solve(int)'
collect2: error: ld returned 1 exit status