Submission #1234257

#	Time	Username	Problem	Language	Result	Execution time	Memory
1234257		coco2311	Global Warming (CEOI18_glo)	C++17	0 / 100	139 ms	13440 KiB

glo

#include <iostream>
#include <cmath>
#include <set>
#include <vector>
#include <algorithm>
using namespace std;

#define f first
#define s second

vector<int> compress(int N, vector<int> v){
    pair<int,int> arr[N];
    for(int i=0;i<N;i++){
        arr[i].f=v[i];
        arr[i].s=i;
    }
    sort(arr,arr+N);
    int bef=arr[0].f+1,cnt=-1;
    for(int i=0;i<N;i++){
        if(arr[i].f!=bef){
            cnt++;
            bef=arr[i].f;
        }
        arr[i].f=arr[i].s;
        arr[i].s=cnt;
    }
    vector<int> res;
    sort(arr,arr+N);
    for(int i=0;i<N;i++){
        res.push_back(arr[i].s);
    }
    return res;
}



int LIS(int N, vector<int> v){  //N , compressed vector
    set<int> se;
    int zp=1<<(int)ceil(log2(N));
    int seg[2*zp]={0};
    se.insert(-1);
    se.insert(N+1);
    for(int i=0;i<N;i++){
        auto lb=se.lower_bound(v[i]);
        lb--;
        if(*lb<0){
            se.insert(v[i]);
            int l=v[i]+zp;
            seg[l]=max(seg[l],1);
            l/=2;
//            cout<<v[i]<<" "<<i<<" "<<1<<'\n';
            while(l>=1){
                seg[l]=max(seg[l+l],seg[l+l+1]);
                l/=2;
            }
            continue;
        }
        else{
            se.insert(v[i]);
            int l=zp,r=(*lb)+zp;
            int m=0;
            while(l<=r){
                if(l%2==1){
                    m=max(m,seg[l]);
                    l++;
                }
                if(r%2==0){
                    m=max(m,seg[r]);
                    r--;
                }
                l/=2;
                r/=2;
            }
            m+=1;
            r=v[i]+zp;
            seg[r]=max(seg[r],m);
            while(r>=1){
                seg[r]=max(seg[r],m);
                r/=2;
            }
//            cout<<v[i]<<" "<<i<<" "<<m<<'\n';
        }
    }
    int m=0;
    for(int i=0;i<2*zp;i++){
        m=max(m,seg[i]);
    }
    return m;
}

int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//    freopen("input.in","r",stdin);
    int N;cin>>N;
    vector<int> v(N);
    for(int i=0;i<N;i++){
        cin>>v[i];
    }
    v=compress(N,v);
    int r = LIS(N,v);
    cout<<r;
}

• Subtask 1: 0 / 5
• Subtask 2: 0 / 10
• Subtask 3: 0 / 13
• Subtask 4: 0 / 10
• Subtask 5: 0 / 20
• Subtask 6: 0 / 17
• Subtask 7: 0 / 25