Submission #62815378

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define ll long long

ll t[400000];

void update(int v, int tl, int tr, int pos, int new_val) {
    if (tl == tr) {
        t[v] = new_val;
    } else {
        int tm = (tl + tr) / 2;
        if (pos <= tm)
            update(v*2, tl, tm, pos, new_val);
        else
            update(v*2+1, tm+1, tr, pos, new_val);
        t[v] = max(t[v*2], t[v*2+1]);
    }
}

int query(int v, int tl, int tr, int l, int r) {
    if (l > r) 
        return 0;
    if (l == tl && r == tr) {
        return t[v];
    }
    int tm = (tl + tr) / 2;
    return max(query(v*2, tl, tm, l, min(r, tm)),
               query(v*2+1, tm+1, tr, max(l, tm+1), r));
}

void solve() {
    ll n, q;
    cin >> n >> q;
    map<ll, vector<ll>> mp;
    vector<ll> v(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> v[i];
        mp[v[i]].push_back(i);
    }
    vector<pair<ll, ll> > queries;
    map<ll, vector<ll> > mpq;
    set<ll> st;
    for(int i=1;i<=q;i++) {
        ll r, x;
        cin>>r>>x;
        queries.push_back({r, x});
        mpq[x].push_back(r);
        st.insert(x);
    }
    map<pair<ll, ll>,  ll> dp;
    for(auto it:mp) {
        ll x = it.first;
        map<ll, ll> temp;
        // cout<<"x = "<<x<<endl;
        for(auto bt:it.second) {
            ll pos = bt;
            // cout<<pos<<" ";
            ll val = query(1, 1, n, 1, pos-1);
            temp[pos] = val + 1;
        }
        while(st.size() and *st.begin() < x) {
            ll y = *st.begin();
            st.erase(st.begin());
            ll ans = 0;
            for(auto r:mpq[y]) {
                ans = query(1, 1, n, 1, r);
                dp[{r, y}] = ans;
            }
        }
        // cout<<endl;
        for(auto bt:it.second) {
            ll pos = bt;
            update(1, 1, n, pos, temp[pos]);
        }
        while(st.size() and *st.begin() <= x) {
            ll y = *st.begin();
            st.erase(st.begin());
            ll ans = 0;
            for(auto r:mpq[y]) {
                ans = query(1, 1, n, 1, r);
                dp[{r, y}] = ans;
            }
        }
        
        // for(int i=1;i<=n;i++) {
        //     cout<<query(1, 1, n, i, i)<<" ";
        // }
        // cout << endl;
    }

    while(st.size()) {
        ll y = *st.begin();
        st.erase(st.begin());
        ll ans = 0;
        for(auto r:mpq[y]) {
            ans = query(1, 1, n, 1, r);
            dp[{r, y}] = ans;
        }
    }

    // cout<<query(1, 1, n, 1, n)<<'\n';

    for(auto it : queries) {
        ll l = it.first;
        ll r = it.second;
        // cout<<l<<" "<<r<<" ";
        cout << dp[{l, r}] << "\n";
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int t=1;
    // cin>>t;
    for(int i=1;i<=t;i++) {
        // cout<<"Case #"<<i<<": ";
        solve();
    }
    return 0;
}

Submission Info

Judge Result