Submission #1129642

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129642		alecurse	Global Warming (CEOI18_glo)	C++20	10 / 100	216 ms	7176 KiB

glo

#include <iostream>
#include <vector>
#include <algorithm>
#include <assert.h>
using namespace std;
int reals=1;
vector<int> tree;

void add(int k, int x, int y, int l, int r, int val) {
    if(y<=l||x>=r) return;
    if(x>=l&&y<=r) {
        tree[k]=val;
        return;
    }
    int d = (x+y)/2;
    add(k*2,x,d,l,r,val);
    add(k*2+1,d,y,l,r,val);
    tree[k]=max(tree[k*2],tree[k*2+1]);
}

int getmax(int k, int x, int y, int l, int r) {
    if(y<=l||x>=r) return 0; 
    if(x>=l&&y<=r) {
        return tree[k];
    }
    int d = (x+y)/2;
    return max(getmax(k*2,x,d,l,r),getmax(k*2+1,d,y,l,r));
}
bool comp(pair<int,int> &a, pair<int,int> &b) {
    if(a.first==b.first) {
        return a.second>b.second;
    }
    return a.first<b.first;
}
int main() {
    // freopen("input.txt","r",stdin);
    // freopen("output.txt","w",stdout);
    int N,X;
    cin>>N>>X;
    assert(X==0);
    vector<int> dp(N);
    vector<int> v(N);
    vector<pair<int,int> > vtosort(N);
    for(int i=0;i<N;i++) {
        cin>>v[i];
        vtosort[i].first=v[i];
        vtosort[i].second=i;
    }
    sort(vtosort.begin(),vtosort.end(),comp);
    vector<int> indexes(N);
    for(int i=0;i<N;i++) {
        indexes[vtosort[i].second]=i;
    }
    while(reals<N)
        reals*=2;
    tree.resize(reals*2);
    for(int i=0;i<N;i++) {
        int maxbef = getmax(1,0,reals,0,indexes[i]);
        dp[i]=maxbef+1;
        add(1,0,reals,indexes[i],indexes[i]+1,dp[i]);
    }
    // int maxres=0;
    // for(int i=0;i<N;i++) {
    //     maxres=max(maxres,dp[i]);
    // }
    tree.clear();
    tree.resize(reals*2);
    vector<int> newdp(N);
    for(int i=N-1;i>=0;i--) {
        int maxbef = getmax(1,0,reals,indexes[i],reals);
        newdp[i]=maxbef+1;
        add(1,0,reals,indexes[i],indexes[i]+1,newdp[i]);
    }
    int maxres=0;
    for(int i=0;i<N;i++) {

        maxres=max(maxres,newdp[i]);
    }
    cout<<maxres;
}

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