Submission #1235802

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235802		clemmy14	Global Warming (CEOI18_glo)	C++20	100 / 100	408 ms	27824 KiB

glo

#include<bits/stdc++.h>
using namespace std;

const int INF=1e9;

struct SegTreeMax {
    int n; vector<int> s;
    SegTreeMax(int n) : s(2*n), n(n) {}
    void update(int pos, int val) {
        for(s[pos+=n]=val; pos/=2;) {
            s[pos]=max(s[pos*2], s[pos*2+1]);
        }
    }
    int query(int b, int e) {
        int ra=-INF, rb=-INF;
        for(b+=n, e+=n; b<e; b/=2, e/=2) {
            if(b%2) ra=max(ra, s[b++]);
            if(e%2) rb=max(rb, s[--e]);
        }
        return max(ra, rb);
    }
};

signed main() {
    int n, x; cin >> n >> x;
    vector<int> v(n);
    for(int i=0; i<n; i++) cin >> v[i];
    vector<int> reNum=v;
    for(int i=0; i<n; i++) reNum.push_back(v[i]-x);
    sort(reNum.begin(), reNum.end());
    int cnt=1;
    map<int, int> m; m[-INF]=0;
    for(int i=0; i<reNum.size(); i++) {
        if(!m.count(reNum[i])) {
            m[reNum[i]]=cnt;
            cnt++;
        }
    }
    // for(auto x : reNum) cout << x << ' ';
    // cout << endl;
    SegTreeMax org(cnt), minus(cnt);
    int ans=0;
    for(int i=0; i<n; i++) {
        int posO=m[v[i]], posN=m[v[i]-x];
        //cout << posO << ' ' << posN << endl;
        int newValO=max(org.query(0, posO), minus.query(0, posO))+1;
        org.update(posO, newValO);
        int newValM=minus.query(0, posN)+1;
        minus.update(posN, newValM);
        ans=max(ans, max(newValO, newValM));    
        // for(int j=0; j<cnt; j++) cout << org.query(j, j+1) << ' ';
        // cout << endl;
        // for(int j=0; j<cnt; j++) cout << minus.query(j, j+1) << ' ';
        // cout << endl << endl;
    }
    cout << ans;
    return 0;
}

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